1

$g(n) = g( \lfloor {n/2}\rfloor) + \lfloor{log_2{n}}\rfloor \\ g(0) = 0$

Series is like this:

$0,0,1,1,3,3,3,3,6,6,6,6,6,6,6,6,10,...$ and it's changes similar as $\lfloor{log_2{n}}\rfloor $

$0,0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,....$

But I can't find smart closed-formula, that's easy to proof.

$g(n) = g(\frac{n}{2}) + \lfloor{log_2{n}}\rfloor for \ even$ and

$g(n) = g(\frac{n-1}{2}) + \lfloor{log_2{n}}\rfloor for \ odd$

My guess was $g(n) = \lfloor log_2{\lfloor\frac{n}{2}\rfloor} \rfloor +\lfloor log_2n\rfloor $ but I am having problem proving this one, even though it's seems to be true :S Could you tell me if im on the right track? Any help very appreciated

Machiaweliczny
  • 489

1 Answers1

4

Hint: Start by considering $g(N)$ for $N = 2^n$. Notice in this case that $$ g(2^n) = g(2^{n-1}) + n = g(2^{n-2}) + (n-1) + n = \ldots = g(0) + 1 + 2 + \ldots + n = \frac{n(n+1)}{2} = \frac{(\log_2 N)^2 + \log_2N}{2}. $$ Now look at the general case.

Dan
  • 7,951