Supposing $b > 1$ and $x \geq 1$, the pseudocode algorithm
L := 0
while x >= b do
L := L + 1
x := x / b
end do
return L
returns $\lfloor \log_b x \rfloor$. (CS aside: If $b$ is an integer, this gives an exact result when all variables have type int
. If the variables have type, e.g., float
, possibly this algorithm can suffer from rounding errors.) For any $x$ the while loop is run $\lfloor \log_b x \rfloor + 1$ times, so this algorithm has complexity $O(\log x)$ in $x$.
Some of the answers already provided get close to a full explanation, but not quite.
Recall that if $b > 1$ and $x > 0$, and $$\log_b x = y,$$ what this means is that $b^y = x$. In other words, the base-$b$ logarithm of $x$ is an exponent $y$ such that when the base $b$ is raised to the $y^{\rm th}$ power, the result is $x$. This is the definition of a (real-valued) logarithm.
So, why is it that for two bases $a$, $b$, $$\frac{\log_a x}{\log_b x}$$ is a constant not dependent on $x$? The reason is that $\log_a x$ is an exponent, say $y$, such that $a^y = x$; and $\log_b x$ is an exponent, say $w$, such that $b^w = x$; then $$b^w = x = a^y.$$ And now, raising both sides to the $1/w$ power, we get $$b = (b^w)^{1/w} = (a^y)^{1/w} = a^{y/w}.$$ So the ratio $y/w$ does not depend on $x$. In fact, again using the definition of logarithm, $y/w$ is the exponent for which the base $a$ must be raised to yield $b$; that is, we explicitly have $$\frac{y}{w} = \log_a b,$$ and from this, we get (with one additional algebraic step) what is known as the "change-of-base" formula $$\frac{\log_a x}{\log_a b} = \log_b x.$$
Note that only the definition of $\log$ was used, and the rule for exponents $(b^m)^n = b^{mn}$.
Best Answer
The series $\displaystyle\sum_{k\ge1}\frac{\log_{2}(\frac{k^{2}}{2})}{k^{2}}$ converges. Let $S$ denote its sum. Then $$ \sum_{k = 1}^{\log_{2}(n)} \frac{n\log_{2}(\frac{k^{2}}{2})}{k^{2}}=nS-\left(n\frac{\log\log n}{\log n}\right)x_n, $$ where $x_n\to+1$.
Edit In fact (see comment below), the OP is interested in $T_n=nS_i(x)$ for $i=\lfloor \log_2(n)\rfloor$ and $x=\frac12$, where, for every $i$ and $x$, $$ S_i(x)=\sum_{k=1}^i(k-1)x^k=\sum_{k=0}^{i-1}kx^{k+1}=x^2U'_i(x),\quad U_i(x)=\sum_{k=0}^{i-1}x^{k}. $$ The function $x\mapsto U_i(x)$ is the sum of a geometric series, hence, for every $x\ne1$, $$ U_i(x)=\frac{1-x^i}{1-x},\qquad U'_i(x)=\frac1{(1-x)^2}(1+ix^i-x^i-ix^{i-1}). $$ Using $x=\frac12$, this yields $$ T_n=n(1-(i+1)2^{-i}). $$ Since $i=\lfloor \log_2(n)\rfloor$, one gets $$ n-2(\log_2(n)+1)<T_n<n-\log_2(n), $$ hence $T_n=n-\Theta(\log_2(n))$. The sequence of general term $(T_n-n)/\log_2(n)$ has the interval $[-2,-1]$ as limit set.