Time Complexity

#1

Can u derive the time complexity for this algo

#2

hi @lcs2019022,

  • In each iteration or in each recursive call, the search gets reduced to half of the array.
  • So for n elements in the array, there are logn(base 2) iterations or recursive calls.

Here a more mathematical way of seeing it, though not really complicated :

The question is, how many times can you divide N by 2 until you have 1? This is essentially saying, do a binary search (half the elements) until you found it. In a formula this would be this:

1 = N / 2 ^ x

multiply by 2 ^ x:

2 ^ x = N

now do the log2:

log2(2 ^ x) = log2 N
x * log2(2) = log2 N
x * 1 = log2 N

this means you can divide log N times until you have everything divided. Which means you have to divide log N (“do the binary search step”) until you found your element.

Doubt regarding time complexity
#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.