The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
Facebook Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions. For hardcopy of previous year questions please see
here
Recent questions tagged mastertheorem
0
votes
1
answer
1
Master's Theorem: Validity of Format
How to check if a given recurrence relation is in a format that is valid to apply Master’s Theorem? Also, how to distinguish between Master’s Theorem and extended Master’s Theorem?
asked
Jun 12
in
Algorithms
by
lolster
(
233
points)

84
views
algorithms
mastertheorem
timecomplexity
asymptoticnotations
0
votes
0
answers
2
Cormen Edition 3 Exercise 4.6 Question 3 (Page No. 106)
Show that case 3 of the master theorem is overstated, in the sense that the regularity condition $af(n/b)\geq cf(n)$ for some constant $c<1$ implies that there exists a constant $\epsilon >0$ such that $f(n)=\Omega(n^{log_ba+\epsilon})$.
asked
Apr 5
in
Algorithms
by
akash.dinkar12
Boss
(
41.4k
points)

18
views
cormen
algorithms
recurrenceeqation
mastertheorem
descriptive
difficult
0
votes
0
answers
3
Cormen Edition 3 Exercise 4.6 Question 2 (Page No. 106)
Show that if $f(n)=\Theta(n^{log_ba}\lg^kn )$, where $k\geq0$ then the master recurrence has solution $T(n) =\Theta(n^{log_ba} \lg^{k+1}n)$.For simplicity, confine your analysis to exact powers of $b$.
asked
Apr 5
in
Algorithms
by
akash.dinkar12
Boss
(
41.4k
points)

13
views
cormen
algorithms
recurrenceeqation
mastertheorem
descriptive
difficult
0
votes
0
answers
4
Cormen Edition 3 Exercise 4.5 Question 5 (Page No. 97)
Consider the regularity condition $af(n/b) \leq cf(n)$ for some constant $c<1$,which is part of case 3 of the master theorem. Give an example of constants $a\geq 1$ and $b>1$ and a function $f(n)$ that satisfies all the conditions in case 3 of the master theorem except the regularity condition.
asked
Apr 5
in
Algorithms
by
akash.dinkar12
Boss
(
41.4k
points)

22
views
cormen
algorithms
recurrenceeqation
mastertheorem
descriptive
difficult
0
votes
0
answers
5
Cormen Edition 3 Exercise 4.5 Question 4 (Page No. 97)
Can the master method be applied to the recurrence $T(n)=4T(n/2)+n^2\ lg\ n$ ?Why or why not? Give an asymptotic upper bound for this recurrence.
asked
Apr 5
in
Algorithms
by
akash.dinkar12
Boss
(
41.4k
points)

16
views
cormen
algorithms
recurrenceeqation
mastertheorem
descriptive
0
votes
0
answers
6
Cormen Edition 3 Exercise 4.5 Question 3 (Page No. 97)
Use the master method to show that the solution to the binarysearch recurrence $T(n)=T(n/2) + \Theta(1)$ is $T(n)=\Theta(lg\ n)$.
asked
Apr 5
in
Algorithms
by
akash.dinkar12
Boss
(
41.4k
points)

13
views
cormen
algorithms
recurrenceeqation
mastertheorem
descriptive
0
votes
0
answers
7
Cormen Edition 3 Exercise 4.5 Question 2 (Page No. 97)
Professor Caesar wishes to develop a matrixmultiplication algorithm that is asymptotically faster than Strassen's algorithm. His algorithm will use the divide and conquer method, dividing each matrix into pieces of size ... value of $a$ for which Professor Caesar's algorithm would be asymptotically faster than Strassen's algorithm?
asked
Apr 5
in
Algorithms
by
akash.dinkar12
Boss
(
41.4k
points)

15
views
cormen
algorithms
recurrenceeqation
mastertheorem
descriptive
0
votes
0
answers
8
Cormen Edition 3 Exercise 4.5 Question 1 (Page No. 96)
Use the master method to give tight asymptotic bounds for the following recurrences. $T(n)=2T(n/4) + 1$ $T(n)=2T(n/4) +\sqrt{n}$ $T(n)=2T(n/4) +n$ $T(n)=2T(n/4) +n^2$
asked
Apr 5
in
Algorithms
by
akash.dinkar12
Boss
(
41.4k
points)

14
views
cormen
algorithms
recurrenceeqation
mastertheorem
0
votes
0
answers
9
master theorem
what is master theorem for function like T(n) = aT(nb) + f(n) where f(n) is not in the form of $n^k$
asked
Dec 13, 2018
in
Algorithms
by
Hira Thakur
Boss
(
13.2k
points)

74
views
mastertheorem
0
votes
0
answers
10
Doubt  Source : Stack_Overflow
How the case is matched ? : T(n) = 2T(n/2) + O(n * m) we have a = 2, b = 2, c = 1 and c = $Log_ba$ (case 2) Hence, T(n) = O(n * m * log n) Now, substituting m with n T(n) = O(n2 * log n)
asked
Nov 27, 2018
in
Algorithms
by
HeadShot
Active
(
4.8k
points)

53
views
mastertheorem
0
votes
0
answers
11
Master's theorem
asked
Oct 20, 2018
in
Algorithms
by
Verma Ashish
Loyal
(
9.8k
points)

103
views
mastertheorem
timecomplexity
0
votes
4
answers
12
Can we solve the recurrence T(n) = T(n/2) + 2^n by masters theorem, if possible?
asked
Sep 28, 2018
in
Algorithms
by
mohitrai0_0
(
331
points)

532
views
recurrence
algorithms
mastertheorem
timecomplexity
asymptoticnotations
0
votes
0
answers
13
Master's Theorem Recurrence Relation
T (n) = T (n/2) + 2n Using Master's Method What is the Complexity Of This Recurrence Relation? Or Using AnyOther Method?
asked
Aug 20, 2018
in
Algorithms
by
pradeepchaudhary
Active
(
1.2k
points)

211
views
algorithms
recurrence
timecomplexity
mastertheorem
0
votes
1
answer
14
MadeEasy Subject Test: Algorithms  Recurrence
which of the following cannot be solved using masters theorem? a) T(n) = 2T(n/2) + n/logn b) T(n) = 2T(n/2) + logn c)T(n)=T(n/2)+logn d) non of these
asked
Aug 11, 2018
in
Algorithms
by
manvi_agarwal
(
99
points)

162
views
madeeasytestseries
recurrence
mastertheorem
0
votes
2
answers
15
masters theorem
Solution using back substitution method T(n) = 2T(n/2) + nlogn ? detailed solution please. ans is nlognlogn or n(logn)^2
asked
Aug 10, 2018
in
Algorithms
by
manvi_agarwal
(
99
points)

108
views
timecomplexity
algorithms
mastertheorem
asymptoticnotations
recurrence
0
votes
0
answers
16
self doubt
consider the following c program A A(n) { if(n<=1) return (n2+n+1); else return ( 5A(n/2)+ 3A(n/2)+n2 } find time complexity T(n)=?
asked
Aug 8, 2018
in
Algorithms
by
hitendra singh
Active
(
1.7k
points)

91
views
algorithms
mastertheorem
0
votes
1
answer
17
Masters Theorem
How can we apply Masters theorem to these equations : T(n) = 16*T(n/4) + n! and T(n) = 4*T(n/2) + cn Please explain the process.
asked
Aug 6, 2018
in
Algorithms
by
Rahul Ranjan 1
(
129
points)

154
views
mastertheorem
timecomplexity
algorithms
asymptoticnotations
recurrence
0
votes
0
answers
18
Master theorem rules
On which of the following recurrence relation Master Theorem cannot be applied? a) T(n)=2T(n/2)+nlogn b) T(n)=T(n/2)+1 c) T(n)=8T(n/2)+logn d) T(n)=7T(n/4)+n^2
asked
Aug 1, 2018
in
Algorithms
by
Sandy Sharma
Active
(
1.2k
points)

105
views
algorithms
mastertheorem
0
votes
1
answer
19
Masters theorem
Solve by using master's theorem
asked
Jul 17, 2018
in
Algorithms
by
bts
(
119
points)

119
views
timecomplexity
mastertheorem
algorithms
asymptoticnotations
recurrence
0
votes
3
answers
20
Masters theorem
Solve using Master's Theorem $T(n)=T(n/2)+$ 2n
asked
Jul 16, 2018
in
Algorithms
by
Vishnathan
(
481
points)

112
views
mastertheorem
algorithms
timecomplexity
0
votes
4
answers
21
Made easy work book
How to solve T (n)=T (sqrt n)+ n
asked
Jun 22, 2018
in
Algorithms
by
Priyanka Agarwal
Active
(
2.3k
points)

92
views
mastertheorem
+2
votes
1
answer
22
Extended Master's Theorem $T(n)=n^{1/2}T(n^{1/2})+n$
Can Extended Masters theorem be applied to the following recursive equation ? $T(n)=n^{1/2}T(n^{1/2})+n$ I solved this using back substitution and the time complexity came out to be $O(n*(loglogn))$ I was wondering if this ... masters theorem, like the way Tauhin Gangwar has solved here  https://gateoverflow.in/60532/findtctn2tn121
asked
Jun 11, 2018
in
Algorithms
by
Hardik Maheshwari
(
87
points)

377
views
timecomplexity
algorithms
mastertheorem
asymptoticnotations
recurrence
+6
votes
3
answers
23
Time complexity , Recursion
Why is recursive equation of following code $T(n)=T(n/2)+O(1)$, not $T(n)=8*T(n/2)+O(1)$? int x=0; int A(n) { if(n==1) return 1; else { X+=8A(n/2)+n^3; } return X; }
asked
May 29, 2018
in
Algorithms
by
bts
(
119
points)

231
views
recursion
timecomplexity
algorithms
mastertheorem
0
votes
1
answer
24
Uttrakhand Asst. Professor Exam62
The running time of an algorithm $T(n)$, where $n$ is the input size, is given by following: $T(n) = \begin{cases} 8T(n/2) + qn & \text{ if } n>1 \\ p & \text{ if } n = 1 \end{cases}$ where $p$ and $q$ are constants, the order of algorithm is $n^2$ $n^3$ $n$ $n^n$
asked
Mar 2, 2018
in
Others
by
gatecse
Boss
(
16.1k
points)

51
views
uttarakhandasstprof2018
algorithms
recurrence
mastertheorem
+2
votes
1
answer
25
recurrence using Master theorem
can we solve this T(n) = T(n/2) + 1 using master theorem?
asked
Jan 11, 2018
in
Algorithms
by
iarnav
Loyal
(
8k
points)

248
views
algorithms
mastertheorem
timecomplexity
recurrence
asymptoticnotations
+7
votes
1
answer
26
T(n) = T(n/4) + T(3n/4) +n
How to solve above recurrence relation (With substitution method)??
asked
Jan 8, 2018
in
Algorithms
by
anoop yadav 2
(
87
points)

1.2k
views
algorithms
mastertheorem
recurrence
timecomplexity
recursion
+3
votes
0
answers
27
Master theorem and extended Master theorem
I have doubt regarding Master theorem.In which situation we should use Normal Master theorem/extended Master theorem?
asked
Jan 8, 2018
in
Algorithms
by
Sona Barman
Active
(
1.2k
points)

547
views
algorithms
mastertheorem
timecomplexity
+2
votes
1
answer
28
Ace Test series: Algorithms  Recurrence
asked
Jan 6, 2018
in
Algorithms
by
smsubham
Loyal
(
9.2k
points)

106
views
acetestseries
timecomplexity
mastertheorem
recurrence
algorithms
+1
vote
1
answer
29
Master Theorem
T(n) = 2T(n/2) + nlogn a. O(nlogn) b.n(log^2n) c.O(n^2)
asked
Dec 19, 2017
in
Algorithms
by
ashwina
Active
(
1.7k
points)

108
views
algorithms
mastertheorem
timecomplexity
0
votes
0
answers
30
Master theorem
T(n) = T(n1) + n In which case it falls ??
asked
Nov 22, 2017
in
Algorithms
by
aka 53
(
235
points)

85
views
algorithms
timecomplexity
mastertheorem
Page:
1
2
3
next »
Quick search syntax
tags
tag:apple
author
user:martin
title
title:apple
content
content:apple
exclude
tag:apple
force match
+apple
views
views:100
score
score:10
answers
answers:2
is accepted
isaccepted:true
is closed
isclosed:true
Recent Posts
Previous Years Question Papers : ISI  MMA, PCB, DCG
Previous Years Question Papers : CMI  Computer Science
Minimum Number of States in a DFA accepting a binary number divisible by 'n'
GATE 2020 Application Form Opened!
My GATE Preparation Journey
Follow @csegate
Recent questions tagged mastertheorem
Recent Blog Comments
Feedback for next edition (if ever there's...
Is go book still available,I want to buy it
will pdfs be uploaded ?
50,092
questions
55,266
answers
190,799
comments
86,083
users