Use app×
Join Bloom Tuition
One on One Online Tuition
JEE MAIN 2025 Foundation Course
NEET 2025 Foundation Course
CLASS 12 FOUNDATION COURSE
CLASS 10 FOUNDATION COURSE
CLASS 9 FOUNDATION COURSE
CLASS 8 FOUNDATION COURSE
0 votes
59 views
in Information Technology by (85.3k points)
closed by
Consider the recurrence function \(T\left( n \right) = \left\{ {\begin{array}{*{20}{c}} {2T\left( {\sqrt n } \right) + 1,\;\;\;n > 2}\\ {2,\;\;\;0 < n \le 2} \end{array}} \right.\) Then T(n) in terms of Θ notation is
1. Θ (log log n)
2. Θ (log n)
3. Θ (√n)
4. Θ (n)

1 Answer

0 votes
by (88.5k points)
selected by
 
Best answer
Correct Answer - Option 2 : Θ (log n)

\(T\left( n \right) = 2\;T\left( {\sqrt n } \right) + 1\)

Put n= 2m, m = log2n

\(T\left( {{2^m}} \right) = 2T\left( {{2^{\frac{m}{2}}}} \right) + 1\)

\(Put\;T\left( {{2^m}} \right) = S\left( m \right)\)

\(S\left( m \right) = 2\;S\;\left( {\frac{m}{2}} \right) + 1\)

Now, calculate \({n^{log_b^a}}\)

\({m^{log_b^a}} = m\)

S (m) = m + 1

S(m) = m

Put the value of m 

Therefore, T(n) in terms of Θ notation is Θ (logn).

Welcome to Sarthaks eConnect: A unique platform where students can interact with teachers/experts/students to get solutions to their queries. Students (upto class 10+2) preparing for All Government Exams, CBSE Board Exam, ICSE Board Exam, State Board Exam, JEE (Mains+Advance) and NEET can ask questions from any subject and get quick answers by subject teachers/ experts/mentors/students.

Categories

...