Question Details

Consider the following recurrence relations:
For all n > 1 ,

T1 (n) = 4 T1 ( n 2 ) + T2 (n) T2 (n) = 5 T2 ( n 4 ) + Θ ( log 2 n ) Assume that for all n ≤ 1 , T1 (n) = 1 and T2 (n) = 1 .
Which one of the following options is correct?

Options

A

T1(n) = Θ(n2)

B

T1(n) = Θ(n2log2n)

C

T1(n) = Θ(nlog45)

D

T1(n) = Θ(nlog45log2 n)

Show Answer
Correct Answer
A
T1(n) = Θ(n2)

Solution :

The correct option is: T1(n) = Θ(n2)

To find the asymptotic tight bound for T1(n), we need to solve the system of recurrence relations step-by-step.

Step 1: Solve the recurrence for T2(n)
The recurrence relation for T2(n) is given by:
T2 (n) = 5 T2 ( n 4 ) + Θ ( log 2 n )
We can solve this using the Master Theorem, which has the general form:
T (n) = a T ( n b ) + f (n)
For T2(n), we have:
• a=5
• b=4
• f(n)=Θ(log2n)
Now, we compare f(n) with nlogba=nlog45.
Since log45≈1.161, we have nlog45≈n1.161.
Clearly, f(n)=O(log2n) grows much slower than nlog45. Formally, f(n)=O(nlog45-ε) for any 0<ε≤0.16.
By Case 1 of the Master Theorem, the recurrence is dominated by the leaf level, yielding:
T2 (n) = Θ ( n log 4 5 )

Step 2: Solve the recurrence for T1(n)
Now, substitute the asymptotic behavior of T2(n) into the recurrence relation for T1(n):
T1 (n) = 4 T1 ( n 2 ) + Θ ( n log 4 5 )
Applying the Master Theorem again:
• a=4
• b=2
• f(n)=Θ(nlog45)
Now we calculate nlogba=nlog24=n2.
We compare the exponent of f(n) which is log45≈1.161 with the exponent 2.
Since 1.161<2, we have f(n)=O(n2-ε) for a positive constant ε (such as ε≈0.839).
Once again, by Case 1 of the Master Theorem, the recurrence is dominated by the leaf cost:
T1 (n) = Θ ( n2 )

Transparent Access on Mindyard

Built for Learners & Educators Alike

Completely free for students. Educators & coaching institutes get 2 months free Pro trial to create tests.

FREE FOR STUDENTS

Practice & Learn Free for Students

Access unlimited practice questions, detailed step-by-step solutions, and exam study materials — completely free for students.

  • Unlimited mock tests & question bank practice
  • Full access to curated study library & formula notes
  • 100% free for students • No credit card required
2 MONTHS FREE TRIAL

Educators & Coaching Institutes

Create and conduct professional online assessments with AI question generation, tab proctoring, and comprehensive batch management.

  • AI question uploader & rapid test generator
  • Anti-cheating tab proctoring & performance reports
  • Full Pro access free for 60 days • No upfront commitment
Discover more resources

You may also like

Mock Tests

View All
  • GATE
  • beginner
  • 3 hours
  • civil engineering

Prepare for GATE 2026 Civil Engineering with the latest question papers, previous year papers, detailed solutions, syllabus, exam pattern, preparation tips, mock tests, and subject-wise study material. Download GATE 2026 CE question papers with solutions in PDF format and boost your preparation for top engineering institutes and PSU recruitment.

  • GATE
  • beginner
  • 3 hours
  • electronics and communication engineering

Prepare effectively for GATE 2026 Electronics & Communication Engineering (EC) with this comprehensive Question Paper with Solutions. This resource includes detailed explanations, concept-wise solutions, previous year paper analysis, and exam-oriented practice to help aspirants strengthen core subjects like Electronic Devices, Analog Circuits, Digital Circuits, Signals & Systems, Network Theory, Control Systems, Electromagnetics, Communications, and more. Perfect for revision, self-assessment, and boosting your GATE 2026 EC preparation strategy.

Ask AI Tutor
5 left
Q1 View Question & Options
AI Tutor is solving this question...
Reading question context & options...
Ask your own doubt or choose a quick prompt: