Time complexity of a recursive algorithm with nested iterative function?

Question

a)

void f(n){
  if(n<=1) return;
    else{
      g(n); //g(n) is O(N^2).
      f(n/2);
      f(n/2);
    } 
}

b)

void f(n){
  if(n<=1) return;
    else{
      g(n); //g(n) is O(N).
      f(n-1);
      f(n-1);
    } 
}

c)

void f(n){
  if(n<=1) return;
    else{
      g(n); //g(n) is O(N^2).
      f(n-1);
      f(n-1);
    } 
}

How do I count the O(n) complexity of the above two code snippet?

a) I got the answer O(n^2), because each f(n) calls itself twice recursively. And since the depth of the tree is LogN (n/2), the overall complexity is O(n^2), do i disregard the g(n) method since it is N^2 as well?

b) Since the depth of the tree is N, and each f(n) calls itself twice recursively. And since each level needs to perform g(n) operation N times, I got the answer O(N.2^(N)).

c) Same as b) but g(n) is performed N^2 time - hence O(N^2.2^(N)).

Is this correct?

Bonje Fir · Accepted Answer · 2018-03-10 13:47:02Z

2

a) The recursive equation is as bellow.

If you expand the recursion we have:

So we want to calculate last equation which is equal to:

Since the last part of above equation is a geometric serie we have:

So the recursion is .

b) The approach is same as before.

which is equal to:

So the answer is

c) Third part can solve with the same technique.

PS: Thanks to Alexandre Dupriez for his comment.

PS: For an elegant simplification of the summation read Alexandre's comments bellow.

edited Mar 10, 2018 at 13:47

answered Mar 8, 2018 at 8:57

Bonje Fir

8388 silver badges27 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

Alexandre Dupriez Over a year ago

for b) and c), it seems to me that complexity is O(2^n) - the reason is in the second term of T(n) = 2^n + n.sum(2^i), n cannot be factored as the sum are respectively n + 2.(n - 1) + ... + 2^n for (b) and n^2 + 2.(n-1)^2 + ... + 2^n.

Bonje Fir Over a year ago

@AlexandreDupriez Thanks for your correction, I missed the decreasing part of that part. I edited the answer. Please check it again.

Alexandre Dupriez Over a year ago

Agreed with the result theta(2^n) - not sure how you get to the simplification of the sums? Anyway, I wouldn't bother too much about getting an exact expression for the partial sum - I'd just justify by the fact that sum(2^i.(n-i)) = 2^n.sum((n-i)/2^(n-i)) = 2^n.sum(k/2^k) and it happens the series of general term k/2^k converges to a finite number (let's call it c) and since the finite sum is increasing, sum(k/2^k) <= c so 2^n.sum(k/2^k) <= c.2^n and since we can find a lower bound of the form d.2^n for another d < c, you get the theta(2^n).

Alexandre Dupriez Over a year ago

Same reasoning with the series sum(k^2/2^k) - and more generally with any integer p, sum(k^p/2^k) always converges to a finite number - so we can generalize the exercises above with g(n) having a complexity of the form O(n^p) for any given integer p.

Alexandre Dupriez Over a year ago

We can also generalize further for any complexity g(n) such that the series sum(g(n)/2^n) is finite, which in particular gives us access to anything of the form a1.n^p1.log(n)^q1 + a2.n^p2.log(n)^q2 + ... for any a1, a2, ...; p1, p2...; q1, q2..., etc.

|

Collectives™ on Stack Overflow

Time complexity of a recursive algorithm with nested iterative function?

1 Answer 1

7 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

7 Comments

Your Answer

Sign up or log in

Post as a guest

Related