Register

Self doubt
closed

• closed by
372 views

1 Answer

1 votes
1 votes

@abhinav dongre

 

Can we transform it into a recurrence with a more usual form :

T(12n)

=T(4n)+T(3n)+5(12n)

=T(4n/3)+T(n)+20n+T(3n/4)+T(n)+15n+60n

=2T(n)+105n+T(4n/3)+T(3n/4) ….

 

So, that’s pretty close to 4T(n)+105n ..

The recurrence T′(n)

=4T′(n/12)+105n/12 ….

 

can be approached with the Master Theorem,

which tells us that c =log124 ≈ 0.56, and 105n is Ω(nc),

 

so T′(n), if regular, is Θ(n)..

 

 

1. https://gateoverflow.in/191487/T-n-t-n-4-t-3n-4-n

 

User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
1 answer
1
Çșȇ ʛấẗẻ asked Mar 14, 2023
423 views
self doubt
Solve the following recurrences using recursion tree method and write the asymptotic time complexity T(n)=T(n/2)+n^2
Solve the following recurrences using recursion tree method and write the asymptotic time complexity T(n)=T(n/2)+n^2
User Avatar
1 votes
1 votes
0 answers
2
srestha asked May 19, 2019
633 views
Recurrence Relation-Self Doubt(Discrete Math+Algo)
Let $A(n)$ denotes the number of $n$ bit binary strings which have no pair of consecutive $1’s.$ what will be recurrence relation for it and what will be it’s Time Complexity??
Let $A(n)$ denotes the number of $n$ bit binary strings which have no pair of consecutive $1’s.$ what will be recurrence relation for it and what will be it’s Time Co...
User Avatar
0 votes
0 votes
1 answer
3
jatin khachane 1 asked Jan 2, 2019
352 views
Self Doubt[Gate Question]
Let T(n) be a function defined by the recurrence T(n)=2T(n/2)+√n for n≥2 andT(1)=1 Can someone please explain solution of this using back substitution
Let T(n) be a function defined by the recurrence T(n)=2T(n/2)+√n for n≥2 andT(1)=1Can someone please explain solution of this using back substitution
User Avatar
0 votes
0 votes
0 answers
4
eyeamgj asked Nov 19, 2018
505 views
SELF DOUBT MADEESY TEST
WHAT IS RECURRENCE RELATION ? I M GETTING T(n-2)+1
WHAT IS RECURRENCE RELATION ?I M GETTING T(n-2)+1
User Avatar
Link Copied!