The time complexity of linear search algorithm over an array of n elements is
A. | O (log2 n) |
B. | O(n) |
C. | O(n log2 n) |
D. | 0 (n2) |
Option: B Explanation :
Linear search has linear-time complexity; binary search has log-time complexity.
Here is a table that provides some intuition about the running speeds of algorithms
Logarithmic: Linear:
array size | N
--------------------------------------------------------
8 | 8
128 | 128
256 | 256
1000 | 1000
100,000 | 100,000 ....
Binary search and other divide-and-conquer algorithms have logN time complexity; we say O(logN)
Linear search have linear time complexity: O(N). So the option is 'B'
Click on Discuss to view users comments. |
The time required to search an element in a linked list of length n is
A. | O(log2 n) |
B. | O(n) |
C. | O(1) |
D. | 0 (n2) |
Option: B Explanation : Click on Discuss to view users comments. |
The worst case time required to search a given element in a sorted linked list of length n is
A. | O(1) |
B. | O(log2 n) |
C. | O(n) |
D. | O(n log2 n) |
Option: C Explanation : Click on Discuss to view users comments. |
Which of the following sorting algorithms does not have a worst case running time of O(n2)?
A. | Insertion sort |
B. | Merge sort |
C. | Quick sort |
D. | Bubble sort |
Option: B Explanation : Click on Discuss to view users comments. |
For a linear search in an array of n elements the time complexity for best, worst and average case are ......., ....... and ........ respectively
A. | O(n), O(1), and O(n/2) |
B. | O(1), O(n) and O(n/2) |
C. | O(1),O(n) and O(n) |
D. | O(1), O(n) and (n-1/2) |
Option: C Explanation : Click on Discuss to view users comments. vikrant said: (5:30pm on Saturday 4th May 2013)
it should be n/2 because it is half of the no;s
kripa said: (11:33am on Thursday 1st October 2015)
then there will not be any difference btween avg case And worst casesince we know theta shows avg case its alwz less then o(n) worst case might be be it can be equal but heresenario says it should be o(n/2)
|
Syllabus covered in this section is-
This Section covers Data Structures Questions Answers using C language .
Who can benefit -
Various Search Terms used for this section are