Question

How to get the big-O for the following recursion relation:T(1)=1, T(2)=1.5, T(N)=1.5T(N/2)-0.5T(N/4)-1/N.

Answer 1

T(1) 1

T(2) 1.5

(w) -15те) -05т- 0.57() ..) = N

Using substitution method to solve this relation

2 r-15те-0эт- .(2) 1.57( 0.5T(- N

1.5T)-0.5T)- N .(3)

Replacing values of (2) and (3) in (1)

2 G.757 3 N T(N) 2.25T( 0.75T( N 0.25T + 16 0.75T(

T(N) 2.25T( +0.25T 16 ...A fter 2 times N

Again replacing values of T(N/4), T(N/8) and T(N/16)

, N N N )- 3.375T ( )+ 1.125T ()-0.125T ( 64 T(N) 3.375T( .After 3 times 16 32

Let's assume N = 2^K => K = log₂N

2K 2K 2K T(N) 3.375T ()-3.375T ( +1.125T ()-0.125T )- 16 2K ..A fter 3 times 2K 8 64

After K times

2K 2K C1TK) -C2T+1)C3T(+- C4T+)+ C5T(; 2K 2K T(N) 2K 2K+4 = 2K 2! K

K T(N) CiT() CT)+CaT-CiT C5T( 16

$\small = 1 - \frac{1}{2} + \frac{1}{4} - \frac{1}{8} + \frac{1}{16}-\frac{1}{32}+..... - \frac{K}{2^K}$

$\small =(1).(-\frac{1}{2})^{k} - \frac{K}{2^K}$

$\small =(1).(-\frac{1}{2})^{log_2N} - \frac{log_{2}N}{N}$

$\small = \frac{1}{N} - \frac{log_2N}{N}$

$\small = O(logN)$