edited by
1,259 views
0 votes
0 votes

Successful Search 

we assume that the probability of searching or finding an element at each location is same , then if we have n elements so probability is $1/n$...

Also we might need to perform $1$ comparison or $2$ or $3$ or $4$ and so on ..

Therefore  average time complexity is $=1.1/n+2.1/n+3.1/n.....n.1/n$

$=(n+1)/2$

 

I am not getting why are we not considering the case when the element is not found at the previous indexes after reaching the current index at which the element is found .

According to me it should be $1*1/n + (1-1/n)*(1/n) + (1-1/n)(1-1/n)*(1/n)$ ............(Considering the case when element if not found at 1st index , is found at 2nd index , then if not found at 2nd index is found at 3rd index and so on .

 

For unsuccessful search , I am not getting the method for calculating the average case using probability ? 

 

Also do we make any assumption while calculating the time complexity for the array , is the order of elements defined in the array is fixed or it can vary ? Please explain precisely .

edited by

Please log in or register to answer this question.

Related questions

0 votes
0 votes
0 answers
1
Sanjay Sharma asked Dec 7, 2017
1,239 views
Average case complexity of sequential search if the element that is searched is not in the lista) ( n+p) /2 b) (np+1)/2 c) n(1-p/...
0 votes
0 votes
1 answer
3
LavTheRawkstar asked Jan 12, 2017
809 views
INSERTION-SORT (A, n) ⊳ A[1 . . n]for (j ← 2 to len(A) ){key ← A[ j];i ← j – 1 ; while (i 0 and A[i] key) { A[...
0 votes
0 votes
2 answers
4
dhruba asked Jun 5, 2023
1,094 views
Binary search is performed on a sorted array of n elements. The search key is not in the array and falls between the elements at positions m and m+1 (where 1 ≤ m < n). ...