Mergesort recurrence

[eline83]

Hello guys.

I'm stuck at my algorithm assignment.

Here is the problem.

We found that the solution to the mergesort recurrence

f(n) = f(┏n/2┓) + f(└n/2┘) + n, f(1) = 0

satisfied f(n) = Θ(nlogn). Find an expression for the exact value of f(n). (Hint: generate the first 20 to 40 values and find a pattern. Prove your conjecture by induction on the number of bits required to express n.)

I calculate the oupput by a short program.

f(n) = 0,2,5,8,12,16,20,24,29, ... , 54,59,64,70,76,82,.....,154,160,167,.....
(where n is 1,2,3,4,......)

f(8) = 24, f(16) = 64, f(32) = 160

I can't find a pattern :(

Help me guys!!

[nezachem]

Another hint: take the differences of your sequence (that is, f(n) - f(n - 1)). You will see the pattern very clearly.

[eline83]

I tried.

I got 2 3 3 4 4 4 4 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 ....

one 2, two 3's, four 4's, eight 5's, fifteen 6's, and 7...

Is there a pattern here???? Can't see T_T

[mike_2000_17]

I think you counted one 6 too few in that last post about the differences.

Also, with the numbers "f(8) = 24", "f(16) = 64", "f(32) = 160"... and the formula "f(n) = O(nlogn)"... I mean.. talk about obvious! I'm no psychic, but I would predict also that "f(64) = 384", "f(128) = 896", "f(256) = 2048"...