# A Proof for Master Theorem 主定理证明

###The Master Theorem:

Let $T(n)$ be a function defined on nonegative integers and taking positive value, if it satisfies $T(n) = a T (\frac{n}{b}) + f(n)$ for $a \geq 1,b \geq 1$, then

1. If $f(n) = \Theta( n^c )$ where $% $, then $T(n) = \Theta( n^{log_b a} )$.
2. If $f(n) = \Theta( n^c log^k n )$ where $c = log_b a$, then $T(n) = \Theta( n^c log^{k+1}n )$.
3. If $f(n) = \Theta( n^c )$ where $c > log_b a$, then $T(n) = \Theta( f(n) )$.

###Proof:

Let’s first set $f(n) = \Theta(n^c)$ a weaker problem and think about the recursion tree for this recurrence. There will be $log_b n$ levels. At each level, the number of subproblems will be multiplied by $a$, and so the number of subproblems at level $i$ will be $a^i$. Each subproblem at level $i$ is a problem of size $(\frac{n}{b^i})$, which needs another $\Theta((\frac{n}{b^i})^c)$ work. So the total number of units of work on level $i$ is $\Theta(a^i (\frac{n}{b^i})^c ) = \Theta( n^c (\frac{a}{b^c})^i )$

In general, we have the total work done is $\sum_{i=0}^{log_b n} \Theta( n^c (\frac{a}{b^c})^i ) = \Theta( n^c \sum _{i=0}^{log_b n} (\frac{a}{b^c})^i )$

In Case 1, we see $\frac{a}{b^c} > 1$, so we have $\sum _{i=0}^{log_b n} (\frac{a}{b^c})^i = \Theta( (\frac{a}{b^c})^{log_b n} )$ when

So Case 1 holds.

In Case 3, we have $% $, then $\sum _{i=0}^{log_b n} (\frac{a}{b^c})^i$ 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 $\frac{a}{b^c} = 1$ and change the work done on level $i$ to

Then in general the total work needs done is

So Case 2 holds. $\square$

example.cpp文件：

# A bash code for jekyll easy post

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

# 自建Mac系统的TimeMachine时光机器备份服务器

Mac的Timemachine是一个很有特色的增量式备份系统。我一直认为这种安全性质的软件实现的方式应当是静默的、后台的，所以 Timemachine有一个好搭档就是TimeCapsule，时光胶囊，苹果自家的无线路由器+网络存储，通过bonjour协议实现了Mac系统的自动访问、 自动挂载和自动备份。

• 路由
• 一台服务器主机，或是主机上的虚拟机，搭载了linux系统
• 服务器和待备份的mac电脑接入同一内网，并确保548端口可用

netatalk是linux下afp的开源实现，用来建立网络共享

avahi是bonjour的开源实现，通过这个服务mac会自动检测到内网上的文件服务器

Ok，现在回到mac，应该可以自动搜索到备份服务器了，输入你linux的用户密码就能自动备份了。