CODEWITHSUNDEEP
arraysperformancealgorithmdata-structurestime-complexity
discoverAnkit
discoverAnkit

Reputation: 1151

Finding the time complexity of code

Given is an infinite sorted array containing only numbers 0 and 1. Find the transition point efficiently.

For example : 00000000000111111111111111

Output : 11 which is the index where the transition occurs

I have coded a solution for this ignoring some edge cases.

int findTransition(int start)
{
  int i;
  if(a[start]==1)return start;
  for(i=1;;i*=2)
  {  
    //assume that this condition will be true for some index
    if(a[start+i]==1)break;
  }
  if(i==1)return start+1;
  return findTransition(start+(i/2));
}

I am not really sure about the time complexity of this solution here. Can someone please help me in figuring this out?

Is it O(log(N))?

Upvotes: 1

Views: 307

Answers (1)

Lurr
Lurr

Reputation: 861

Let n be position of transition point

This block

for(i=1;;i*=2)
  {  
    //assume that this condition will be true for some index
    if(a[start+i]==1)break;
  }

works for log2(n)

So we have

T(n) = log2(n) + T(n/2)
T(n) = log2(n) + log2(n/2) + T(n/4) = log2(n) + (log2(n) - 1) + (log2(n) - 2)... 
T(n) = log2(n) * (log2(n) + 1) / 2

So there is O(log(n)^2) complexity (for worst case)

Note: you can use usual binary search instead of recursion call, then you will have log2(n) + log2(n/2) just O(log(n)) granted.

Upvotes: 5

Related Questions