0

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.

John Kugelman
  • 349,597
  • 67
  • 533
  • 578
nullPointer
  • 37
  • 1
  • 4
  • 1
    What are "infinite integers"? And how is this any different from an ordinary binary search? – Fred Foo Apr 23 '13 at 15:52
  • 1
    http://en.wikipedia.org/wiki/Binary_search_algorithm – kassak Apr 23 '13 at 15:53
  • The number of integers is unknown, assuming it as infinite. – nullPointer Apr 23 '13 at 15:53
  • Previous question on SO [here](http://stackoverflow.com/questions/5329937/search-algorithm-and-its-complexity) and [here](http://stackoverflow.com/questions/6196896/why-to-consider-binary-search-running-time-complexity-is-as-log2n). The first link talks about an /infinite/ array and binary search. – S.R.I Apr 23 '13 at 15:57
  • 2
    If you are assuming the numbers can be infinitely large, then you can't assume that your arithmetic operators are O(1). – mbeckish Apr 23 '13 at 15:57

2 Answers2

1

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)
siddstuff
  • 1,215
  • 4
  • 16
  • 37
0

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

Tim S.
  • 55,448
  • 7
  • 96
  • 122