Confused about time complexity of recursive function

user_5330107 0
Viewed 34

For the following algorithm (this algorithm doesn't really do anything useful besides being an exercise in analyzing time complexity):

const dib = (n) => {
  if (n <= 1) return;
  dib(n-1);
  dib(n-1);

I'm watching a video where they say the time complexity is O(2^n). If I count the nodes I can see they're right (the tree has around 32 nodes) however in my head I thought it would be O(n*2^n) since n is the height of the tree and each level has 2^n nodes. Can anyone point out the flaw in my thinking?

dynamic-programming time-complexity
2 Answers

Each tree has 2^i nodes, not 2^n.

So each level has 2^(i-1) nodes: 1 + 2 + 4 + 8 ... 2^n. The deepest level is the decider in the complexity.

The total number of nodes beneath any level > 1 is 1 + 2*f(i-1) . This is 2^n - 1.

user_133222590

Derek's answer is great, it gives intuition behind the estimation, if you want formal proof, you can use the Master theorem for Decreasing functions.

The master theorem is a formula for solving recurrences of the form T(n) = aT(n - b) + f(n), where a ≥ 1 and b > 0 and f(n) is asymptotically positive. (Asymptotically positive means that the function is positive for all sufficiently large n.

Recurrent formula for above algorithm is T(n) = 2*T(n-1) + O(1). Do you see why? You can see solution for various cases (a=1, a>1, a<1) here http://cs.uok.edu.in/Files/79755f07-9550-4aeb-bd6f-5d802d56b46d/Custom/Ten%20Master%20Method.pdf

For our case a>1, so T(n) = O(a^(n/b) * f(n)) or O (a^(n/b) * n^k ) and gives O(2^n)

user_99267210
Related