CODEWITHSUNDEEP
performancerecursionbig-o
GalaxyVintage
GalaxyVintage

Reputation: 666

Running time of a recursive algorithm

I came across a question asking what the running time of the following recursive algorithm is.

  int func(int A[], unsigned int len)
  {      if(len==1) return A[0];

         unsigned int mid=len/2;
         int a=func(A,mid); //first half
         int b=func(A+mid,len-mid);//second half

         if(a<b) return b;
         else return a;
  }

This code simply returns the biggest value of a given array.

The answer is O(N), but I just don't know how to justify it.. (my first guess was O(logN)...but it seems like it is incorrect...)

Upvotes: 2

Views: 785

Answers (1)

templatetypedef
templatetypedef

Reputation: 372684

This is a great spot to write out a recurrence relation. Each recursive call does a constant amount of work comparing values and computing the halfway point of the array, then makes two recursive calls, each on something half the size of the original. Writing that out as a recurrence relation, we get

T(n) = 2T(n / 2) + O(1)

You can then use the Master Theorem to solve this, which solves out to O(n). Alternatively, you could think about the shape of this recursion tree. Each level doubles the number of recursive calls, and the number of levels will be O(log n) because you're repeatedly cutting n in half. This means that the number of total calls is 1 in the first layer, 2 in the second, 4 in the third, 8 in the fourth, etc. Summing this gives

1 + 2 + 4 + 8 + 16 + ... + n

= 20 + 21 + 22 + ... + 2log n

= 2(log n + 1) - 1

= 2n - 1

= O(n)

Hope this helps!

Upvotes: 2

Related Questions