CODEWITHSUNDEEP
algorithmbig-o
Britney Tu
Britney Tu

Reputation: 35

Recursive function runtime

1.Given that T(0)=1, T(n)=T([2n/3])+c (in this case 2n/3 is lower bound). What is big-Θ bound for T(n)? Is this just simply log(n)(base 3/2). Please tell me how to get the result.

2.Given the code

void mystery(int n) {
   if(n < 2)
      return;
   else {
      int i = 0;
      for(i = 1; i <= 8; i += 2) {
         mystery(n/3);
      }
      int count = 0;
      for(i = 1; i < n*n; i++) {
         count = count + 1;
      }
   }
}

According to the master theorem, the big-O bound is n^2. But my result is log(n)*n^2 (base 3) . I'm not sure of my result, and actually I do not really know how to deal with the runtime of recursive function. It is just simply the log function?

Or what if like in this code T(n)=4*T(n/3)+n^2?

Cheers.

Upvotes: 3

Views: 687

Answers (2)

Adi Levin
Adi Levin

Reputation: 5233

Let's do some complexity analysis, and we'll find that the asymptotic behavior of T(n) depends on the constants of the recursion.

Given T(n) = A T(n*p) + C, with A,C>0 and p<1, let's first try to prove T(n)=O(n log n). We try to find D such that for large enough n

T(n) <= D(n * log(n))

This yields

A * D(n*p * log(n*p)) + C <= D*(n * log(n))

Looking at the higher order terms, this results in

A*D*p <= D

So, if A*p <= 1, this works, and T(n)=O(n log n).

In the special case that A<=1 we can do better, and prove that T(n)=O(log n):

T(n) <= D log(n)

Yields

A * D(log(n*p)) + C <= D*(log(n))

Looking at the higher order terms, this results in

A * D * log(n) + C + A * D *log(p) <= D * log(n)

Which is true for large enough D and n since A<=1 and log(p)<0.

Otherwise, if A*p>1, let's find the minimal value of q such that T(n)=O(n^q). We try to find the minimal q such that there exists D for which

T(n) <= D n^q

This yields

A * D p^q n^q + C <= D*n^q

Looking at the higher order terms, this results in

A*D*p^q <= D

The minimal q that satisfies this is defined by 

A*p^q = 1

So we conclude that T(n)=O(n^q) for q = - log(A) / log(p).

Now, given T(n) = A T(n*p) + B n^a + C, with A,B,C>0 and p<1, try to prove that T(n)=O(n^q) for some q. We try to find the minimal q>=a such that for some D>0,

T(n) <= D n^q

This yields

A * D n^q p^q + B n^a + C <= D n^q

Trying q==a, this will work only if 

ADp^a + B <= D

I.e. T(n)=O(n^a) if Ap^a < 1.

Otherwise we get to Ap^q = 1 as before, which means T(n)=O(n^q) for q = - log(A) / log(p).

Upvotes: 0

templatetypedef
templatetypedef

Reputation: 372784

For (1), the recurrence solves to c log3/2 n + c. To see this, you can use the iteration method to expand out a few terms of the recurrence and spot a pattern:

T(n) = T(2n/3) + c

= T(4n/9) + 2c

= T(8n/27) + 3c

= T((2/3)k n) + kc

Assuming that T(1) = c and solving for the choice of k that makes the expression inside the parentheses equal to 1, we get that

1 = (2/3)k n

(3/2)k = n

k = log3/2

Plugging in this choice of k into the above expression gives the final result.

For (2), you have the recurrence relation

T(n) = 4T(n/3) + n2

Using the master theorem with a = 4, b = 3, and d = 2, we see that logb a = log3 4 < d, so this solves to O(n2). Here's one way to see this. At the top level, you do n2 work. At the layer below that, you have four calls each doing n2 / 9 work, so you do 4n2 / 9 work, less than the top layer. The layer below that does 16 calls that each do n2 / 81 work for a total of 16n2 / 81 work, again much work than the layer above. Overall, each layer does exponentially less work than the layer above it, so the top layer ends up dominating all the other ones asymptotically.

Upvotes: 1

Related Questions