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$
    – Lubin
    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$
    – Allen More
    Jun 11, 2018 at 0:04
  • 1
    $\begingroup$ Possible duplicate of Formula for calculating $\sum_{n=0}^{m}nr^n$ $\endgroup$ Jun 11, 2018 at 7:23

2 Answers 2

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$
    – Allen More
    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$ 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$ Sep 12, 2019 at 23:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.