287 views

1 Answer

2 votes
2 votes
f(n) = $\Theta (g(n))$

if c1.g(n) $\leq$ f(n) $\leq$ c2.g(n)

f(n) =  $\frac{n^2}{2} - \frac{n}{2}$  and g(n) = $n^2$

f(n) $\leq$ 1.g(n)  as $\frac{n^2}{2} - \frac{n}{2}$ $\leq$ $n^2$, hence we have found C2 as 1.

now find C1 such as $C1.n^2$ $\leq$ $\frac{n^2}{2} - \frac{n}{2}$

As given in solution above C1 = $\frac{1}{5}$ will staisfy our condition
edited

Related questions

2 votes
2 votes
0 answers
2
Rajeev Kumar 1 asked Jan 9, 2018
761 views
T(N)=3T((N/3)+5)+N/2what will be the time complexity?
0 votes
0 votes
2 answers
3
Arnab Bhadra asked Jun 30, 2017
1,974 views
Use recursion tree method to determine Upper Bound ofT(n) = T(n-1) + T(n/2) + n
0 votes
0 votes
3 answers
4
Anmol Verma asked Jan 9, 2017
1,465 views
1) T(n)=T(n-1)+1/n.2) T(n)=T(n-1) +1/log(n)3)T(n)=3T((n/3) - 2)+n/2.4)T(n)=T(n/2)+T(n/4)+T(n/8)+n.Use Masters theorem