Remember
Register
Algorithms Q&A
Smart HCM Software
Get the course textbook
Questions
Unanswered
Ask a Question
Lecture Notes
Not Exponential, on Twitter
All categories
Asymptotic Analysis
(22)
D&C
(9)
Greedy
(1)
Dynamic Programming
(7)
Backtracking/DFS/BFS
(2)
Branch & Bound
(2)
Graph Theory
(14)
NPCompleteness
(4)
Most popular tags
timecomplexity
asymptoticnotation
recurrencerelations
loops
asymptoticanalysis
dynamicprogramming
graph
analysis
vertexcoloring
exponent
greedy
log
mvcs
npcompleteness
mastertheorem
smalloh
nestedloops
sortedlists
example
recursive
proxy
network
substitutionmethod
branchandbound
d&c
degreeconstrained
spanningtree
vertexcover
reduction
dfs
subtree
primenumbers
sqrt
lecture1
math
tree
count
minimize
floors
array
median
knapsack
trichotomy
eggs
searching
function
relation
gcd
tetris
Solve the recurrence relation: T(n) = 3 T(n/2) + n^1.5 log n
+2
votes
Solve the recurrence relation: T(n) = 3 T(n/2) + n
^{1.5}
log n
recurrencerelations
timecomplexity
asymptoticanalysis
asked
Dec 14, 2016
in
D&C
by
Amrinder Arora
(
38
points)
Please
log in
or
register
to answer this question.
1 Answer
+1
vote
Best answer
a = 3 > 2^1.5
T(n) =
θ(n^log
_{2}
^{3}
)
answered
Feb 15
by
liyanbo
Active
(
312
points)
selected
Feb 15
by
Amrinder Arora
I don't quite understand why we could get rid of the logn to use master theory to compare log23 with 1.5 .
We now that log n = o(n^0.001) (or any small epsilon). // small oh
Therefore, n^1.5 log n = o (n^1.50001) = o(n^log2(3)) // small oh
And therefore, the Master Theorem allows us to conclude T(n) = θ(n^log2(3))
THX professor.
Please
log in
or
register
to add a comment.
Related questions
+8
votes
4
answers
Solve the recurrence relation: T(n)=T(n/2)+T(n/3)+T(n/4) + n
asked
Feb 14
in
D&C
by
Amrinder Arora
(
38
points)
asymptoticanalysis
recurrencerelations
timecomplexity
+1
vote
1
answer
Solve the recurrence Relation T(n)=T(n/5)+T(7n/10)+(n^2)
asked
Feb 8
in
Asymptotic Analysis
by
shijie
Active
(
276
points)
recurrencerelations
asymptoticanalysis
timecomplexity
+1
vote
3
answers
Solve the recurrence Relation: T(n) = T(n/3) + T(2n/3) + n
asked
Dec 14, 2016
in
D&C
by
Amrinder Arora
(
38
points)
recurrencerelations
substitutionmethod
asymptoticanalysis
+3
votes
2
answers
Recurrence relation : T(n) = T(n/3) + 2 T(2n/3) + n
asked
Sep 15, 2016
in
Asymptotic Analysis
by
panrunyu
AlgoStar
(
400
points)
timecomplexity
recurrencerelations
+3
votes
1
answer
Solve the recurrence relation: T(n)=T(n/2)+T(n^0.5)+n
asked
Mar 2
in
Asymptotic Analysis
by
shijie
Active
(
276
points)
The Book: Analysis and Design of Algorithms

Presentations on Slideshare

Lecture Notes, etc
...