Solve Recurrance Relation E Find Closed Form Formula Determine Theta Nlogn T N 3t N 3 Dn Q37163079

December 7, 2021 by Administrator

Solve it as a recurrance relation, i.e. find theclosed form formula and determine if it is Theta(nlogn)

T(n) = 3T(n/3) + dn

Answer

Solving given recurrence relation:

T(n)=3T(n/3)+dn

=3*3T(n/9)+dn+dn

=3*3*3T(n/27)+dn+dn+dn

=…. …. ….

=3log3n+dn+dn+dn….+dn (log3ntimes)

=n+log3n*dn

$Θ(n log:)$ .

Above solution is also , $(n log n$

Because, log n=(3/2)log3n.

So, nlog3n<=n(1/2)log n, so nlog3n=O(nlog n)

similarly, nlog3n>=n*2log n, so, $n log, n-Ω( n log n )$

Hence, $n log, n-Θ (n log n )$ .

Θ(n log:”) (n log n n log, n-Ω( n log n ) n log, n-Θ (n log n )