One of the most important algorithms is Quicksort. Though its idea is quite simple, Rikka remembers that it took her a while to prove the time complexity. Let f(n) be the expected number of comparisons required by Quicksort on a sequence with length n. Then f(n) follows the following equations:
f(0)f(i)=0=i−1+1i∑j=1i(f(j−1)+f(i−j))i≥1
After some simple derivations, Rikka finishes the proof and obtains the result that f(n)=O(nlogn): As an outstanding undergraduate student, this problem is just a piece of cake for her.
To make the task more challenging, Rikka asks Yuta, her boyfriend, to set several exercises for her. The following is the hardest one of them:
Consider a modified version of Quicksort: the recursive process terminates once the length of the interval is less than m. At this time, the expected number of comparisons gm(n) can be described with the following equations:
gm(i)gm(i)=0=i−1+1i∑j=1i(gm(j−1)+gm(i−j))0≤i≤mi>m
Now, Yuta shows the value of n,m, and he wants Rikka to calculate gm(n). It is generally known that Rikka is not good at math. Therefore she wants you to help her calculate the answer.