where is my mistake ?

nir_g 12 Nov 2009 16:09

Let c be some constant:

2^(log(c,n)) = 2^(log(2,n)/log(2,c)) = {1/log(2,c)=p} = 2^p * 2^(log(2,n)) = 2^p * n **= theta(n);**

From the other hand, according to Corman : a^(lob(b,n)) = n^(log(b,a)) and thus:

2^(log(c,n)) = n^(log(c,2)) **!= theta(n);**