Hint: Consider S(k)=T(2k)+c⋅2k. Show that S(k+1)⩽3S(k). Compute S(0). Deduce that S(k)⩽3k(1+c) for every k⩾0 and, finally, that T(2k)⩽3k+c⋅(3k−2k) for every k⩾0.
Post Question
Please allow ads on our site
Kindly log in to use this feature. We’ll take you to the login page automatically.
LoginQuestion about a recurrence
Course Queries Syllabus Queries 3 years ago
User submissions are the sole responsibility of contributors, with TuteeHUB disclaiming liability for accuracy, copyrights, or consequences of use; content is for informational purposes only and not professional advice.
No matter what stage you're at in your education or career, TuteeHUB will help you reach the next level that you're aiming for. Simply,Choose a subject/topic and get started in self-paced practice sessions to improve your knowledge and scores.
Similar Forum
Explore Other Libraries
Online Exams
Question Bank
Career News
Feeds
Full Forms
Dictionary
Interview Question
Gigs
Quotes
Lyrics
Videos
Courses
Blogs
Tutorials
Forum
Educators
Corporates
Tools
Please allow ads on our site
Kindly log in to use this feature. We’ll take you to the login page automatically.
Login
manpreet![Tuteehub forum best answer]()
Best Answer
3 years ago
In a syllabus of mine, they try to find a closed form of the following recurrence relation
The method I usually use to find the closed form of a recurrence is expand it a few times and try to find a pattern. Then I verify that pattern using induction.
In my syllabus they only show the verification part, by using T(2l)≤c(3l−2l)T(2l)≤c(3l−2l) as hypothesis, where cc is chosen such T(2)≤cT(2)≤c and l≥1l≥1.
So, I tried expanding the recurrence relation to see where I could find that pattern, but I don't get anything close to it.
For example: