I have an exercise problem and don't know why its answer is like this. $$ \sum_{i=1}^{\lg n} 2^{i-1} \in \Theta(2^{\lg n}) = \Theta(n). $$

Regarding this equation, I think it would be, $$ \sum_{i=1}^{\lg n} 2^{i-1} \in \Theta(\lg n \cdot 2^{\lg n}) = \Theta(\lg n \cdot n), $$ with the proof, $$ \sum_{i=1}^{g(n)}f(i) \le \sum_{i=1}^{g(n)}f(g(n)) = g(n)\cdot f(g(n)). $$

My thought with this question, $ f(n) = 2^{i-1} $ and $ g(n)= \lg n $. Then result would be $ \lg n \cdot 2^{\lg n - 1} $.

Can anyone point out where I made a mistake? (I am not asking grading mine, but tell me where I mis-think)

  • 2
    $\begingroup$ This question appears to be unsuited for this site because questions of the form: "This is the exercise problem, this is my solution. Please grade!" are not interesting for anyone but you. Please see this related meta discussion, and these hints on asking questions about exercise problems. If you want to ask a specific question about a specific part of your attempt, please edit the question accordingly. $\endgroup$ – dkaeae Feb 26 '19 at 16:56
  • $\begingroup$ @dkaeae edited my question $\endgroup$ – jayko03 Feb 26 '19 at 17:19
  • 1
    $\begingroup$ @jayko03 Unfortunately, changing the question to 'find my mistake' does not solve the problems that exist with questions requesting to 'check a solution'. You can improve your question by specifically explain where and why you think you have made a mistake. $\endgroup$ – Discrete lizard Feb 26 '19 at 18:36

Your argument shows that $$ \sum_{i=1}^{\lg n} 2^{i-1} = O(n\lg n). $$ It doesn't show the matching lower bound, which is actually false.

| cite | improve this answer | |
  • $\begingroup$ I don't understand where it is from $\endgroup$ – jayko03 Feb 26 '19 at 17:17
  • $\begingroup$ Your proof, as you describe it, only proves the "≤" direction. You also need to prove the "≥" direction. $\endgroup$ – Yuval Filmus Feb 26 '19 at 17:19

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.