Question
Download Solution PDFConsider the recurrence relation :
\(T(n) = 8T \left(\frac{n}{2}\right)+Cn, if \;n > 1\)
= b, if n = 1
Where b and c are constants.
The order of the algorithm corresponding to above recurrence relation is :
Answer (Detailed Solution Below)
Detailed Solution
Download Solution PDFThe correct answer is option 4.
Master's theorem:
\(T(n) = aT \left(\frac{n}{b}\right)+f(n)\) where a > = 1 and b > 1
Case: 1. If f(n) = Θ(nc) where c < Logba then T(n) = Θ(nlogba)
EXPLANTION
\(T(n) = 8T \left(\frac{n}{2}\right)+Cn, if \;n > 1\)
= b, if n = 1
Where b and c are constants.
The above recurrence is in the form of the
Here, c = Log28 = 3
f(n) = Θ(n3)
Hence the correct answer is n3.
Last updated on Jun 12, 2025
-> The UGC NET June 2025 exam will be conducted from 25th to 29th June 2025.
-> The UGC-NET exam takes place for 85 subjects, to determine the eligibility for 'Junior Research Fellowship’ and ‘Assistant Professor’ posts, as well as for PhD. admissions.
-> The exam is conducted bi-annually - in June and December cycles.
-> The exam comprises two papers - Paper I and Paper II. Paper I consists of 50 questions and Paper II consists of 100 questions.
-> The candidates who are preparing for the exam can check the UGC NET Previous Year Papers and UGC NET Test Series to boost their preparations.