algorithm - 以下复发的时间复杂度？

Question

找出递归的时间复杂度（Big Oh Bound）T(n) = T(⌊n⌋) + T(⌈n⌉) + 1。

这的时间复杂度如何O(n)？

Answer 1

You probably ment T(n)=T(⌊n/2⌋)+ T(⌈n/2⌉) + 1.

Lets calculate first few values of T(n).

T(1) = 1
T(2) = 3
T(3) = 5
T(4) = 7

We can guess that T(n) = 2 * n - 1.

Lets prove that by mathematical induction

Basis

T(1) = 1
T(2) = 3
T(3) = 5
T(4) = 7

Inductive step

T(2*n) = T(⌊2*n/2⌋)+ T(⌈2*n/2⌉) + 1  
   = T(⌊n⌋)+ T(⌈n⌉) + 1 
   = (2*n - 1) + (2*n - 1) + 1 
   = 4*n - 1
   = 2 * (2*n) - 1

T(2*n+1) = T(⌊(2*n+1)/2⌋)+ T(⌈(2*n+1)/2⌉) + 1
   = T(n)+ T(n+1) + 1
   = (2*n - 1) + (2*(n+1) - 1) + 1 = 
   = 4*n + 1 =
   = (2*n+1)*2 - 1

Since both the basis and the inductive step have been proved, it has now been proved by mathematical induction that T(n) holds for all natural 2*n - 1.

T(n) = 2*n - 1 = O(n)

Answer 2