- All categories
- Asymptotic Analysis (22)
- Divide & Conquer (9)
- Greedy Algorithms (2)
- Dynamic Programming (7)
- Backtracking/DFS/BFS (2)
- Branch & Bound (2)
- Graph Theory (15)
- NP-Completeness (4)

+1 vote

Best answer

Assume that T(n)≤cnlgn

So there exist c and m that let T(m)≤cmlgm and when n>=m, let T(n)≤cnlgn.

T(m)=cm/3lg(m/3)+2cm/3lg(2m/3)+m

=cm/3(lgm-lg3)+2cm/3(lgm-lg(3/2))+m

=cmlgm-(cm/3)lg3-(2cm/3)(lg3-lg2)+m

=cmlgm-cmlg3+2cm/3+m

So when we let m+2cm/3-cmlg3<0 the assumption is realized

we could let c=3 m>0 then (3-3lg3)m<0 is assured

So the assumption is demonstrated and T(n)=O(nlgn).

0 votes

Assume T(n) ≤ cnlogn

Prove T(2)=2

T(m) ≤ T(2m/3) + T(2m/3) +m ( 2≤m≤n)

≤ 2c(2m/3)log(2m/3) + m

= (4m/3)cm( log(2/3) + logm) + m

= (4m/3) cmlogm + (4/3) cmlog(2/3) + m

_{= (4/3)} cmlogm - (4/3)cmlog(3/2) +m

= (4/3) cmlogm – m( 4/3 log(3/2) -1)

≈ cmlogm

So T(m) ≤ cmlogm T(n)≤ cnlogn

T(n) = O(nlogn)

This doesn't look correct. Because you say:

4/3 cm log m ~ cmlogm.

Mathematics doesn't really allow that symbol: ~

You need to prove this more clearly.

4/3 cm log m ~ cmlogm.

Mathematics doesn't really allow that symbol: ~

You need to prove this more clearly.

Hello Prof.Arora, what about this prove? Without enlarging the T(n/3) term to T(2n/3).

Prove T(2)=2

T(m) = T(m/3) + T(2m/3) +m ( 2≤m≤n)

≤ c(m/3)log(m/3) + c(2m/3)log(2m/3) + m

= c(m/3)log(1/3) + c(m/3)log(m) + c(2m/3)log(2/3) + c(2m/3)log(m) + m

= cmlogm + c(m/3)log(1/3) + c(2m/3)cmlog(2/3) + m

= cmlogm - (1/3)cmlog(3) - (2/3)cmlog(3/2) +m

= cmlogm – m( (c/3)log(3) + (2c/3)log(3/2) -1)

≈ cmlogm

So T(m) ≤ cmlogm T(n)≤ cnlogn

T(n) = O(nlogn)

Prove T(2)=2

T(m) = T(m/3) + T(2m/3) +m ( 2≤m≤n)

≤ c(m/3)log(m/3) + c(2m/3)log(2m/3) + m

= c(m/3)log(1/3) + c(m/3)log(m) + c(2m/3)log(2/3) + c(2m/3)log(m) + m

= cmlogm + c(m/3)log(1/3) + c(2m/3)cmlog(2/3) + m

= cmlogm - (1/3)cmlog(3) - (2/3)cmlog(3/2) +m

= cmlogm – m( (c/3)log(3) + (2c/3)log(3/2) -1)

≈ cmlogm

So T(m) ≤ cmlogm T(n)≤ cnlogn

T(n) = O(nlogn)

...