0
$\begingroup$

I'm trying to prove analytically the time complexity of a problem in "Cracking The Coding Interview". The algorithm in question involves calling an O(1) operation on each node of a binary tree once for each level of nodes above it and every node in the tree is visited. The cost of such an algorithm, it seems to me would be:

$2^1(1) + 2^2(2) + 2^3(3) + ... + 2^{log_2 n}log_2(n)$ where n is the number of nodes.

I'm not sure how to evaluate the above using the usual equation for finite geometric series: $a_1\frac{(1-r^n)}{(1-r)}$ where $a_1$ is the first value and r is the constant factor by which the series grows, because the series does not seem to grow at a constant factor; r grows with each step of the algorithm. Does this sort of series have a name?

$\endgroup$
3
  • $\begingroup$ Sorry, but I’m too lazy tonight to convert your post to readability by applying the relevant MathJax. Your last term, though, does not seem to fit into the pattern of the three terms you wrote out explicitly. $\endgroup$ Commented Jun 10, 2018 at 23:47
  • $\begingroup$ Sorry, first post, applied MathJax. The summation would increment the exponent and factor by one up until $log_2(n)$ because that would be the number of levels in a balanced binary tree which is the worst case for this algo I should have mentioned. @Lubin $\endgroup$ Commented Jun 11, 2018 at 0:04
  • 1
    $\begingroup$ Possible duplicate of Formula for calculating $\sum_{n=0}^{m}nr^n$ $\endgroup$ Commented Jun 11, 2018 at 7:23

2 Answers 2

Reset to default
2
$\begingroup$

Hint: Note that $(\sum_{i=0}^{n}x^i)'=\sum_{i=0}^{n-1}(i+1)x^i$ and thus $\sum_{i=1}^{n}ix^{i}=\sum_{i=0}^{n-1}(i+1)x^{i+1}=x(\sum_{i=0}^{n}x^i)'=x(\frac{1-x^n}{1-x})'$. Can you take it from here?

$\endgroup$
2
  • $\begingroup$ Got it, thanks. Is there a name for this trick? I feel like I should know this. $\endgroup$ Commented Jun 11, 2018 at 0:29
  • $\begingroup$ I don’t think there is a standard name but you should find similar methods in any book about combinatronics and generating functions/series. $\endgroup$ Commented Jun 11, 2018 at 1:14
1
$\begingroup$

Consider the geometric formula

$$\frac{r^n-1}{r-1} = 1+r+r^2+r^3+...+r^{n-1}$$

We take the derivative on both sides in terms of $r$:

$$\frac{(nr^{n-1})(r-1)-(r^n-1)}{(r-1)^2}=1+2r+3r^2+...+(n-1)r^{n-2}$$

We then multiply both sides by $r$ in order for the coefficient to match the exponent of $r$:

$$r\frac{(nr^{n-1})(r-1)-(r^n-1)}{(r-1)^2}=r+2r^2+3r^3+...+(n-1)r^{n-1}$$

Substituting $r=2$:

$$2[(n2^{n-1})-(2^n-1)]=2(1)+2^2(2)+2^3(3)+...+2^{n-1}(n-1)$$

At this point you're finished, but you can substitute $n=n+1$ so that $n$ equals the number of terms, and we can also simplify the LHS. The final formula is

$$2^{n+1}(n-1)+2$$where $n$ is the number of terms.

$\endgroup$
1
  • 1
    $\begingroup$ Nice work there! $\endgroup$ Commented Sep 12, 2019 at 23:51

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.