CODEWITHSUNDEEP
algorithmrecursionbig-o
J J
J J

Reputation: 93

Big-O Notation for a recursive function

This question has been asked a few times before, but I'm still having trouble finding the answer for this problem because it is more complex than the simple examples provided in the other questions.

I'm trying to find the big O notation for:

float foo(int start, int end, int s)
{
  if (start == end) {
    return start*start;
  } else {
    int iSegment = (end - start + 1) / s;
    int iCurrResult = 0;
    for (int i=0; i<=s; i++)
      iCurrResult += foo (start + i*iSegment, start + (i+1) * iSegment - 1, s);
    return iCurrResult*iCurrResult;
  }
}

Upvotes: 2

Views: 282

Answers (1)

amit
amit

Reputation: 178431

Each time the function is called, it invokes itself recursively s+1 times, with a range of size n/s (n is the number of elements).

This gives you the complexity function:

T(n) = (s+1)T(n/s) + 1

According to Wolphram Alpha, this function is in O((s+1)^(logn/logs)) = O((s+1)^log(n-s))

Note that this is in Omega(n), since n=s^log_s(n)=s^log(n)/log(s), and it is easy to see that this function is strictly (and asymptotically) bigger than s^(logn/logs)

Upvotes: 3

Related Questions