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!!