enter image description here

  1. Why the first part of formula is equal to $2 * 2^2 + ... + 2^{log(n)} = 2^2 + 2^3 +...+ 2^{log(n)} = 2^3 +...+ 2^{log(n)} =... +2^{log(n)}$

  2. What is the logic behind ($2^{log n +1} - 2{log n}$) ?

  3. I don't understand why $2n.log - (2^{log (n+1)} - 2)=Θ(nlogn)$ ? (Please explain what is math logic bihind it)


In the first part where the summation $\sum_{i=1}^{\log n}i2^i$, you see that whole summation can be written as that chain of summations (if you sum them all up you'll end up getting the first form on the top). Then you use the summation of power two's formula, i.e. $\sum_{i=0}^{n}2^i= 2^{n+1}-1$.

In the first line $=2+2^2+...+2^{log n}$ the formula is missing a -1 so the result will be $2^{\log n +1}-2$, the second one is missing a 2 so it will be $2^{\log n+1}-2^2$ and so on.

You can write $2^{\log n +1}$ as $2*2^{\log n}$ which is equal to $2*n$. I think what confuses you is that you think they wrote $2^{\log (n+1)}$ where as it is $2^{\log n +1}$.

As for why the $2n*\log n - (2^{\log n +1} -2) \in \Theta(nlogn)$, since $2n\log n \in \Theta(nlogn)$ and $2^{\log n + 1} = 2*n$ thus it is $\Theta(n)$ and from the property of asyptotic notation we can conclude $\Theta(nlogn)-\Theta(n) \in \Theta(nlogn)$.

| cite | improve this answer | |
  • $\begingroup$ thank you so much ...Then you use the summation of power two's formula, i.e. $\sum_{i=0}^{n}2^i= 2^{n+1}-1$ ? what is exactly meaning? and why -1? $\endgroup$ – Michael Dec 1 '19 at 14:43
  • $\begingroup$ Here is a better and longer explanation of summation of powers of two. It would be to clumped up to answer that in the same post. $\endgroup$ – Yiğit Aras Tunalı Dec 1 '19 at 14:48
  • $\begingroup$ I have several questions! 1. why $2^{\log n +1}-2$ formula is $2^{\log n +1}$ and why add +1 to power ? 2 .why In the first line -1 is missing? and the formula has -2 and if -1 is from missing -1 ... what is another -1? (that sum both is -2) $\endgroup$ – Michael Dec 1 '19 at 14:58
  • $\begingroup$ think of $\log n$ as K, then you can write $2^{K+1}$ and maybe it will be easier for you to make it look like the summation formula. That first line would be the sum of 2's formula but there is no +1 so we can just say it is $(2^{(K+1)}-1)-1$ on the other second line you see it is missing a 2 from the upper one, we wrote the upper one as $(2^{(K+1)}-1)-1$ just subtract -2 from this to get the formula for the second line and so on. Where we said let $K = \log n$ for more readability. $\endgroup$ – Yiğit Aras Tunalı Dec 1 '19 at 15:04
  • $\begingroup$ Why exactly $\Theta(nlogn)-\Theta(n)$ is equal Θ(nlogn) ? can you explain and introduce good source for learning about this! tanks. $\endgroup$ – Michael Dec 1 '19 at 15:13

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.