order of algorithms

**Projectt** · October 26th 2009, 03:54 PM

i'm normally decent with these type of problems but i can't really figure this one out.

show that if n is a power of 2, say n = 2^k, then
$\sum_{i=0}^{k} log(n/2^i) = \Theta (lg^2 n)$

**gmatt** · October 29th 2009, 08:55 AM

Originally Posted by Projectt

i'm normally decent with these type of problems but i can't really figure this one out.

show that if n is a power of 2, say n = 2^k, then
$\sum_{i=0}^{k} log(n/2^i) = \Theta (lg^2 n)$

if n is a power of two then $\sum_{i=0}^{k} log(n/2^i) = \sum_{i=0}^{k} log(2^{k-i}) =\sum_{i=0}^{k} (k-i)log(2)$ $= log(2) \sum_{i=0}^{k} (k-i) \in \Theta(k^2) = \Theta([log_2(n)]^2)$ for some $k = log_2(n)$

Thread: order of algorithms

LinkBack

Thread Tools

Display

order of algorithms

Similar Math Help Forum Discussions

Algorithms

Algorithms

algorithms

Algorithms

Algorithms!

Search Tags