2

I came across this as a good example for understanding the runtime of recursively called functions. There is a good outline of the issue here:https://stackoverflow.com/a/33663627/9750088

However, my misunderstanding comes from summing 2^1 + 2^2.... 2^n-1 as the sum of each level of the recursion tree's calls. To me, this sum of 1+2...n-1 seems to be n(n-1)/2, which intuitively seems to me like n^2 in big O notation, therefore leading to a total runtime of O 2^n^2 in big ) notation. How exactly does that sum of the tree's leaves end up 2^n instead?

ZhaoGang
  • 4,491
  • 1
  • 27
  • 39
antonig
  • 153
  • 1
  • 10
  • 2
    To clear up some confusion: `2^1 + 2^2 + ... + 2^{n-1}` != `2^{1 + 2 + ... + n-1}` for `n > 1`. `2^1 + 2^2 + ... + 2^{n-1}` = `2^{n} - 1`. Also, `2^{1 + 2 + ... + n-1}` = `(2^1) * (2^2) * ... * (2^{n-1})`. – ljeabmreosn Dec 14 '18 at 00:23
  • 1
    As @ljeabmreosn pointed out, your calculation is wrong. Try to use the summing formula of geometric series to calculate the sum of `2^1 + 2^2.... 2^n-1` – lincr Dec 14 '18 at 02:31
  • 1
    Are you asking why sum(2^i, i=1..n-1) isn't the same as 2^sum(i, i=1..n-1)? – Paul Hankin Dec 14 '18 at 08:11
  • 2
    Related: [The idea behind the sum of powers of 2](https://math.stackexchange.com/questions/1990137/the-idea-behind-the-sum-of-powers-of-2) – Bernhard Barker Dec 14 '18 at 10:50

1 Answers1

2

My understanding of the answer in that link:

  1. Firstly you should understand how many nodes in that recursion tree. For a number n, there are 2^(n-1) leaves in the tree, and 2^(n-1)-1 non-leaves nodes.(For the root level, there are 2^0 nodes; second level: 2^1 nodes;... last non-leaf level-the second lowest level: 2^(n-2) nodes. The sum is 2^0+2^1+...+2^(n-2)=2^(n-1)-1. This is important,you can try to find some example and figure it out.) . So there are 2^(n-1)+2^(n-1)-1 nodes totally.
  2. The time complextity then is O(2^(n-1)+2^(n-1)-1)->O(2^(n-1)+2^(n-1))->O(2*2^(n-1))->O(2^n)
ZhaoGang
  • 4,491
  • 1
  • 27
  • 39