# What is the upper bound on $T(n) = 3T(n/2) + n$?

The upper bound on $T(n) = 3T(n/2) + n$ is:

1. $O(n \lg n)$

2. $O(n \lg 3)$

3. $O(n^2)$

4. $O(n \lg n + n)$

-
Welcome to math.SE. Is this a homework problem? What did you try? –  user2468 May 18 '12 at 17:21

Recurrence relations of the form $T(n) = pT(n/q)+n^d$ are common; their solutions are given by what's often known as the Master Theorem. If you look it up, you'll find that your recurrence has a solution bounded by $O(n^\alpha)$ and once you discover what $\alpha$ is the correct choice should jump out at you.

-

Assuming that $T$ is a sequence, it is not clear to me how is $T(n)$ defined, when $n$ is not a power of $2$. By taking into account only the values when $n$ is a power of $2\,$, from $T(n)=3T(n/2)+n$ follows that $T(2^{k})=3T(2^{k-1})+2^{k}$, or $$\frac{T(2^{k})}{3^{k}}=\frac{T(2^{k-1})}{3^{k-1}}+\left( \frac{2}{3}\right) ^{k}%$$ for any $k$. By summing up from $k=1$ to $k=N$, it follows that $$\frac{T(2^{N})}{3^{N}}=T(1)+\sum_{k=1}^{N}\left( \frac{2}{3}\right) ^{k}\text{.}$$ As $N\rightarrow\infty$, we obtain that $$\lim_{N\rightarrow\infty}\frac{T(2^{N})}{3^{N}}=T(1)+2$$ or that $$\lim_{n\rightarrow\infty}\frac{T(n)}{n^{\frac{\ln3}{\ln2}}}=T(1)+2$$ ($2^{N}=n$, hence $N=\frac{\ln n}{\ln2}$, meaning that $3^{N}=3^{\frac{\ln n}{\ln2}}=n^{\frac{\ln3}{\ln2}}$).

Hence, $T(n)=O(n^{a})$, with $a=\frac{\ln3}{\ln2}$.

Edit:

To be more exact, the previous computation leads to: $$T(n)=c\cdot n^{a}-2n$$ where $c=T(1)+2$. In the special case when $T(1)=-2$, then $$T(n)=-2n\text{.}%$$

-
The sum starts at $k=1$, so the result is correct. –  digital-Ink Jul 20 at 6:52

Guess:

T(n) = O(nlg 3)

By definition of Big-O, must find c > 0 and n ≥ n0 > 0

0 ≤ T(n) ≤ cnlg 3 - bn

T(n/2) ≤ c(n/2)lg 3 - bn/2

Induction Step:

T(n) = 3T(n/2) + n Recurrence ≤ 3[c(n/2)lg 3 - bn/2] + n substitution of IH = 3[c(nlg 3/2lg 3) - bn/2] + n
= 3[cnlg 3/3) - bn/2] + n 2lg 3 = 3lg 2 = 3 = cnlg 3 - 3bn/2 + n
≤ cnlg 3 - bn

Find b cnlg 3 - 3bn/2 + n ≤ cnlg 3 - bn n ≤ 3bn/2-bn = 3bn/2-2bn/2 = (3bn-2bn)/2 = bn/2 2n ≤ bn 2 ≤ b b ≥ 2 Base case: Find n0

where T(n) = 1 when n = 1 3T(n/2) + n when n > 1 Verify: 0 ≤ T(n) ≤ cnlg 3 - bn

Try n0 = 2 an even number 3T(n/2) + n ≤ cnlg 3 - bn nlg 3=3lg n 3T(2/2) + n ≤ c3lg 2 - b2 n0=2 3T(1) + 2 ≤ 3c-2b 3lg 2=31 3*1 + 2 ≤ 3c-2b
5 ≤ 3c-2b
2b+5 ≤ 3c
3c ≥ 2b+5 b ≥ 2 3c ≥ 9
c ≥ 3
holds for n0 = 2 and c ≥ 3

1. Choose: c ≥ 3 and n0 = 2

Since T(n) ≤ cnlg 3 - bn, ∀n ≥ n0 when b ≥ 2, c ≥ 3 and n0 = 2

T(n) ∈ O(nlg 3)

-
Did you intend your highlighted line 4 to be a consequence of the line 3 above it? If so, it's not correct--since you have no reason to assume that $T$ is a linear function, it doesn't follow that from $T(n)\le cn\log 3-bn$ you can conclude that $T(n/2)\le c(n/2)-bn/2$. @digital-ink's answer is correct. –  Rick Decker Jul 21 '12 at 20:40