While evaluating the complexity of an algorithm, I got an inequality that I am unable to understand.

Let us consider this series:

$$x= n + (2^0 + 2^1 + 2^2 + \cdots + 2^{\lfloor\log(n-1)\rfloor})$$

How do I prove that $x\leq 3n$ ?

Please help me understand this intuitively or otherwise.


The key is the identity $$ \sum_{i=0}^{m}2^{i} = 2^{m+1}-1 $$

Then just plugging in $m=\lfloor\log(n-1)\rfloor$ we get $$ x = n + (2^{\lfloor\log(n-1)\rfloor+1}-1) $$ It should be obvious from there.


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.