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
Recent questions tagged mastertheorem
+1
vote
2
answers
1
ISRO202021
The master theorem assumes the subproblems are unequal sizes can be used if the subproblems are of equal size cannot be used for divide and conquer algorithms cannot be used for asymptotic complexity analysis
asked
Jan 13
in
Algorithms
by
Satbir
Boss
(
24.2k
points)

125
views
isro2020
algorithms
mastertheorem
easy
0
votes
1
answer
2
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, 2019
in
Algorithms
by
lolster
(
237
points)

114
views
algorithms
mastertheorem
timecomplexity
asymptoticnotations
0
votes
0
answers
3
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.5k
points)

22
views
cormen
algorithms
recurrenceeqation
mastertheorem
descriptive
difficult
0
votes
0
answers
4
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.5k
points)

17
views
cormen
algorithms
recurrenceeqation
mastertheorem
descriptive
difficult
0
votes
0
answers
5
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.5k
points)

30
views
cormen
algorithms
recurrenceeqation
mastertheorem
descriptive
difficult
0
votes
0
answers
6
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.5k
points)

24
views
cormen
algorithms
recurrenceeqation
mastertheorem
descriptive
0
votes
0
answers
7
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.5k
points)

18
views
cormen
algorithms
recurrenceeqation
mastertheorem
descriptive
0
votes
0
answers
8
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.5k
points)

27
views
cormen
algorithms
recurrenceeqation
mastertheorem
descriptive
0
votes
0
answers
9
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.5k
points)

26
views
cormen
algorithms
recurrenceeqation
mastertheorem
0
votes
0
answers
10
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
(
15k
points)

85
views
mastertheorem
0
votes
0
answers
11
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
(
5.1k
points)

57
views
mastertheorem
0
votes
0
answers
12
Master's theorem
asked
Oct 20, 2018
in
Algorithms
by
Verma Ashish
Boss
(
13.1k
points)

135
views
mastertheorem
timecomplexity
0
votes
4
answers
13
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
(
395
points)

719
views
recurrence
algorithms
mastertheorem
timecomplexity
asymptoticnotations
0
votes
0
answers
14
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)

248
views
algorithms
recurrence
timecomplexity
mastertheorem
0
votes
1
answer
15
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
(
111
points)

173
views
madeeasytestseries
recurrence
mastertheorem
0
votes
2
answers
16
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
(
111
points)

118
views
timecomplexity
algorithms
mastertheorem
asymptoticnotations
recurrence
0
votes
0
answers
17
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)

97
views
algorithms
mastertheorem
0
votes
1
answer
18
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)

172
views
mastertheorem
timecomplexity
algorithms
asymptoticnotations
recurrence
0
votes
0
answers
19
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)

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

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

123
views
mastertheorem
algorithms
timecomplexity
0
votes
3
answers
22
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)

100
views
mastertheorem
+2
votes
1
answer
23
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
(
101
points)

447
views
timecomplexity
algorithms
mastertheorem
asymptoticnotations
recurrence
+7
votes
3
answers
24
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
(
129
points)

271
views
recursion
timecomplexity
algorithms
mastertheorem
0
votes
1
answer
25
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
(
17.5k
points)

56
views
uttarakhandasstprof2018
algorithms
recurrence
mastertheorem
+2
votes
1
answer
26
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
(
8.5k
points)

260
views
algorithms
mastertheorem
timecomplexity
recurrence
asymptoticnotations
+7
votes
1
answer
27
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.4k
views
algorithms
mastertheorem
recurrence
timecomplexity
recursion
+3
votes
0
answers
28
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)

615
views
algorithms
mastertheorem
timecomplexity
+2
votes
1
answer
29
Ace Test series: Algorithms  Recurrence
asked
Jan 6, 2018
in
Algorithms
by
smsubham
Boss
(
11.8k
points)

116
views
acetestseries
timecomplexity
mastertheorem
recurrence
algorithms
+1
vote
1
answer
30
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.8k
points)

112
views
algorithms
mastertheorem
timecomplexity
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
ISRO CSE 2020 PAPER ANALYSE
BARC OCES/DGFS 2020
ISI CMI PDF by GATE Overflow
Calculus Important Points
Management Trainee Recruitment COAL INDIA 2020
Follow @csegate
Recent questions tagged mastertheorem
Recent Blog Comments
@nkg_master9  For getting selected for the...
Nowhere it's mentioned.
@bond  Is it mentioned that you have to score at...
I think cutoff won't cross 85
Cut off will be between 95115 not more than that.
50,737
questions
57,378
answers
198,523
comments
105,317
users