Time complexity of the algorithm

Question

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.

What are "infinite integers"? And how is this any different from an ordinary binary search? — Fred Foo
– Fred Foo, Commented Apr 23, 2013 at 15:52
Previous question on SO here and here. The first link talks about an /infinite/ array and binary search. — S.R.I
– S.R.I, Commented Apr 23, 2013 at 15:57
If you are assuming the numbers can be infinitely large, then you can't assume that your arithmetic operators are O(1). — mbeckish
– mbeckish, Commented Apr 23, 2013 at 15:57

siddstuff · Accepted Answer · 2013-04-24 14:52:39Z

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)

Tim S. · Accepted Answer · 2013-04-23 15:53:52Z

0

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

answered Apr 23, 2013 at 15:53

Tim S.

56.7k9 gold badges100 silver badges124 bronze badges

Collectives™ on Stack Overflow

Time complexity of the algorithm

2 Answers 2

Comments

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Linked

Related