Question regarding search algorithm

Question

Is the worst time complexity of following search algo O(n/2) and if yes what is the name of this algo or there is nothing like it ?

a=[i for i in range(100)]
count=0
search=99
for i in range(len(a)):
count+=1
left=i*2+1
right=i*2+2
if left<len(a) and a[left]==search:
print("found")
break
elif right<len(a) and a[right]==search:
print("found")
break

print(count)

Answer 1

Abhay
Logically you are correct, it does not need to search the rest once it reaches halfway.

But, if the element is not in the list, then there is nothing telling the loop to end. This can be fixed by adding another if statement (probably before the other if statements) to check if the left element is within the range. If the left is greater than the range you should break the loop.

This will reduce the worst case number of iterations by half, which is a good improvement. However, asymptotically speaking the big-O is still O(n). (since 1/2 is nothing compared to infinity)

Answer 2

Yes. It get executed i=49 worst case but actually you can't call it worst case if all cases are tested. In your code i=50 to 99 never tested.. We can call worst if search found at last case or no found at all.
So Worst case is o(n).
So it's time complexity this is O(n/2),

I think you have name it but it is similar to linear search. But you are taking 2 searches at a time(i, i+1), redusing number of cases to search.. Instead of single case i...

Answer 3

You can call Worst case if element found at last index ( i=99) or not at all after every case search. But in you case search is found at i=49. (n/2) you have else part also which is reusing cycles..

And no i=50 to 99 never tested, see by printing i values, because left=2*i+1, right=2*i+2 are checking 50 to 99 indexes but not i.
There is heap sort also. But only one algorithm is not best for all type of searching cases. Every algarithm is best for certain, some type of search..
Look at "Algarithms " in community topics.

Edit: https://www.sololearn.com/learn/774/?ref=app

Edit : here you can see heap sort Algarithms and its details of implementation, working,....
Abhay
https://www.programiz.com/dsa/heap-sort
.

Answer 4

Abhay as far I know, its an average case..
Best is O(1). //Loop stopped at first iteration
Worst is O(n). //n=len(a). Loop stopped at last iteration or condition failed.

Answer 5

Jayakrishna🇮🇳 ty for the example , this definitely cleared things a little bit ,also I saw that my algo was doing n iterations when the element isn't found so I changed the for loop to run half the length of list like

for i in range(len(a)/2-1):

So will the worst time complexity be now n/2?

Answer 6

Jayakrishna🇮🇳 but it is running from i=0 to i=50 which checks every element i.e 1-99
So if 99 the last element to be searched is not the worst case ,so what is it? And i am considering the for loop only for time complexity and everything inside it being a constant!!

Answer 7

Abhay The loop is main consideration. Not array element. Search element found at last index in that case but loop is not executing i=0 to 99. Means not 99 cycles. Cycles only 49.
For single statement is time complexity is 1 constant only.. But for loop it is o(n) : n is number of cycles.

Answer 8

Jayakrishna🇮🇳 sorry for asking again but loop only runs for len(list)/2 ,so I still don't get it how is O(n) the worst case

Answer 9

Abhay
Let assume, A student get
Best :
if marks>75
Average
if 40<marks<75 :
Worst badge :
If marks<40.

His best performance when he got >75marks
Average performance when he get 2nd case marks
His worst performance is when he fail.

See can't be 3 cases at a time.
Similarly when loop runs for search n iteration is worst case.
Only ones iteration is best case.
Average performance is best+worst/2 ie : n/2.

The performance is calculating on assumptions. Before running any. And considering performance when you input a best sample(ex: sorted elements) , a worst sample( zigzag samples).. Average is you know why average consider and for what it is considered.
For your program :
If search = 1, your Algarithms result best performance.
If search >=100 or negative numbers.. Algarithms result worst performance.
Average is (best performance + worst performance) /2.
Hope example make sense.. Hope it clears then...

Answer 10

Abhay
The worst case occurs if the element does not exist in the list. If the number of elements is n, the the Big-O would be O(n). (nothing stops the loop if left or right is outside the range of a)

Furthermore, the Big-O complexity is an asymptotic analysis.
Asymptotic being as the input size approaches infinity.
Therefore, only dominant terms are considered. 1/2 is a constant and has no impact on infinity, therefore can be dropped from your expression. (note: that at worst it iterates through n elements anyway, not 1/2 n elements)

Answer 11

Abhay you are ignoring 2nd part of array in your algorithm by taking range(len(a)/2+1).
So here you just making n to n/2 to compare to your original algorithm..
n is constant, n/2 is also constant...
O(n) means you need in loop, 'n' number of iterations..
If 'n', grows iterations grows..
But you may not need all iterations for some inputs..
Here comes best, worst, and hence on some samples average depending on inputs..
Worst case means you search failed.. or algorithm performed poorly.. So it depend on inputs samples that's why we take 'n' calculations..

"asymptomatically speaking the big-O is still O(n)."
Yes, as said n and n/2 still constants.
There I told you about iterations in your algorithm when change to len(a/2).
So worst case comparisons are n/2. But come to general big-O notation worst case O(n/2) =>O(n).

If it is not clear then I try to add a link that better explain to you. if I found any, later may be

Answer 12

Jayakrishna🇮🇳 ty for you answer ,but why can't we call it worst case? The element to be searched is at the end of Array ,so for this algo it is the worst case of it ,am I thinking wrong ? And you said 50 to 99 never tested but they are, every element is checked due to i,i+1 except first one ,

I took this algo from the implementation of heap sort which is used for unsorted array ,but after few searches I found no such algo , looks like there is Linear search and then binary search and other searches ,which would be more efficient for searching,so this wudn't be of any use !!

Answer 13

Jayakrishna🇮🇳 so it has the worst case of o(n/2) ,right ?

Answer 14

Adam McGregor thank you for the answer but why should it iterate through n elements in worst case when it covers all the elements by the time it reaches half the length of list? What is the use of searching beyond that?

Answer 15

Adam McGregor got it ,thank you

Answer 16

like if change "
for i in range(len(a)/2-1):

So will the worst time complexity be now n/2-1?
"

Yes Abhay

Answer 17

Jayakrishna🇮🇳 but as Adam mentioned it will it will still be n 1/2 is constant for infinite number and is ignored ,so I guess it won't be n/2 even if the iterations are half the length of list

Answer 18

Jayakrishna🇮🇳 clear enough ,thank you