2

I'm given to the following relationship:

$$C(x) = C(\lfloor(\frac x2)\rfloor) + x, C(1)=2$$

I do not understand how my teacher says to calculate big O. Any help to start?

Amzoti
  • 56,093
user80490
  • 33

1 Answers1

0

HINT: Put $x=2^n$ and solve to find the series.

  • Thanks for the hint, but that has made me even more lost. – user80490 Jun 01 '13 at 03:35
  • @user80490 Another hint: it will result in a geometric series. – rurouniwallace Jun 01 '13 at 03:36
  • @user80490 Once you get the geometric series you are done. On applying the substitution, the expression becomes $C(2^n) = C(2^{n-1}) + 2^n$. Now continue expanding $C(2^{n-1})$ and so on to get the GP. Find the sum and now replace $2^n $ by $x$. You should get a linear expression. –  Jun 01 '13 at 03:49