Let’s first set a weaker problem and think about the recursion tree for this recurrence. There will be levels. At each level, the number of subproblems will be multiplied by , and so the number of subproblems at level will be . Each subproblem at level is a problem of size , which needs another work. So the total number of units of work on level is
In general, we have the total work done is
In Case 1, we see , so we have
So Case 1 holds.
In Case 3, we have , then
converge to some constance. So we have
So Case 3 holds.
Finally let’s take a look at a little more strict Case 2. Just take and change the work done on level to
Most jekyll user work under unix-like shell. Since I’m not familiar with ruby, ‘rake’ seems hard for me, I wrote a simple bash script to creat new posts. Anyway, it’s quite simple, so take it as a website test! :)