Success TrackerSuccess Tracker
Log inSign up

GATE CS 2026 Set 1 — Question 17

Go beyond PYQs with Success TrackerAI-powered personalised practice and doubt support. Unlimited practice on eligible plans; AI usage limits apply.
MCQ+1 / -0.33MediumMaster TheoremAsymptotic AnalysisAlgorithms

Algorithms → Asymptotic Analysis → Master Theorem

Last updated

Question

Consider the following recurrence relations:
For all n>1n > 1,T1(n)=4T1(n2)+T2(n)T_1(n) = 4T_1\left(\frac{n}{2}\right) + T_2(n)T2(n)=5T2(n4)+Θ(log⁡2n)T_2(n) = 5T_2\left(\frac{n}{4}\right) + \Theta(\log_2 n)Assume that for all n≤1,T1(n)=1n \le 1, T_1(n) = 1 and T2(n)=1T_2(n) = 1.
Which one of the following options is correct?
Your answer

Choose one option, then check your answer.

The solution stays hidden until you check.

Continue learning with Success Tracker

A step still unclear? Work through it with support

Use Success Tracker to ask about the reasoning, then try another GATE CS question to check your understanding.

AI-powered practice· Unlimited practice on eligible plans
PYQs with solutions
Attempt available previous-year questions, then compare your reasoning with the worked solution. Coverage varies by stream.
Practice that adapts
Choose a topic, work on weaker areas and bookmark questions to revisit. Your attempts feed your progress tracking.
AI doubt support
Ask follow-up questions about a step or concept while practising, instead of stopping at the final answer.

Unlimited practice is available on eligible plans. Free practice and AI usage have limits; check the current plan allowances before choosing.

Start with a free accountView plans and allowances

This page stays readable without an account. AI responses can be wrong; check them against the solution and source material.

More questions on Asymptotic Analysis

2026 Set 2 Q24Consider the following functions, where nn is a positive integer.…2026 Set 2 Q25Which of the following can be recurrence relation(s) corresponding to an algorithm with time…2026 Set 2 Q32Consider an array A=[10,7,8,19,41,35,25,31]A = [10, 7, 8, 19, 41, 35, 25, 31]. Suppose the merge sort algorithm is…2026 Set 2 Q37Let GG be a weighted directed acyclic graph with mm edges and nn vertices. Given GG and a…2026 Set 2 Q38Consider an array AA of integers of size nn. The indices of AA run from 1 to nn. An algorithm…