CODEWITHSUNDEEP
algorithmbig-otime-complexitybinary-search
nullPointer
nullPointer

Reputation: 37

Time complexity of the algorithm

I wrote an algorithm for finding a key in sorted array of infinite integers.

 findKey(int k, int start, int end)
     int mid = (start + end)/2

     if (k < array[mid])
         findKey(k, start, mid)
     else if (k > array[mid])
         findKey(k, mid+1, end)
     else 
         return mid

I want to know the time complexity of this algorithm. Is it o(logn)? I'm really confused, can anyone explain? Also let me know if there are any flaws in here. Thanks in advance.

Upvotes: 0

Views: 159

Answers (2)

siddstuff
siddstuff

Reputation: 1255

Let we have array with stored value enter image description here

Suppose we want to find the key=20, we call findkey(20,1,8) with parameters k=20, start=1 and end = 8

Series of function calls

enter image description here

Recurrence relation :

T(n)  = T(n/2)+c
 expanding…
          =T(n/2^2)+c+c
          =T(n/2^3)+c+c+c

Kth time expanding…

          = c+c+c+c+c . .. .. . .. . . .  .T(n/2^k)

Let at kth time array size become 1,
we assume it as a base condition for recurrence.
Thus , 
   n/2^k = 1
      n  = 2^k
Taking log both sides ..
    log n = k

 time complexity of recurrence..

   T(n) = c* log n 
        = O(log n)

Upvotes: 1

Tim S.
Tim S.

Reputation: 56536

What you've made is the binary search algorithm, or something close to it. This algorithm is O(log n).

Upvotes: 0

Related Questions