Member Avatar for 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!!

  • 3 Contributors
  • 3 Replies
  • 108 Views
  • 7 Hours Discussion Span
  • Latest Post Latest Post by mike_2000_17
Member Avatar for nezachem

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

Member Avatar for 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

Member Avatar for 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"...

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.