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