The Gateway to Computer Science Excellence
+2 votes
487 views

Solve this recurrence equation using Master's theorem

T(n) = 64 T(n/8) - n 2 log n

in Algorithms by Boss (33k points) | 487 views
0

Master method cannot be applied, as F(N) = NLog N is decreasing .

+1
$\tt T(n) = 64T(\frac{n}{8}) + n^2log(\frac{1}{n})$
Take on from here.
+1
Still it falls between 1 and 2 .
+1
yup master theorm not apllicable.
0
Akra Bazzi can be easily applied :)
0

Please tell how to apply Akra Bazii in the following recurrence :

T(n)=T(n/2)+ T(n/4) +n2

0
I think Answer is O(n^2).
0

Following 2 case are possible :

1.) For worst case , recurrence relation is

T(n) = 2T(n/2) + n2   {as T(n/2) is larger problem then T(n/4) }

2.) For best case , recurrence relation is 

T(n)= 2 T(n/4) + n2 

4 Answers

0 votes

As this  N2logN Function is decreasing Master Theorem can not be applied here..

by Boss (18k points)
0

what do u mean by (N2   LOG N ) IS DECREASING ?

0 votes
the answer will be T(n)=theta(n^2 log^2 n)
by (15 points)
0 votes
master theorem can't be applied
by (421 points)
0 votes

Using Advanced master's theorem https://www.geeksforgeeks.org/advanced-master-theorem-for-divide-and-conquer-recurrences/
T(n) = Θ($n^{2}$loglogn)

by Junior (677 points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,312 answers
198,343 comments
105,035 users