Login
Register
@
Dark Mode
Profile
Edit my Profile
Messages
My favorites
Register
Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous Years
Blogs
New Blog
Exams
Dark Mode
Recent questions tagged master-theorem
0
votes
1
answer
1
Solve equation using master theorem T(n) = 8T(n/2) + 3n^2
I can't figure out how to proceed and which case it's falling under after calculating h(n)
ItzDc
asked
in
Algorithms
Jun 3
by
ItzDc
331
views
algorithms
recurrence-relation
master-theorem
asymptotic-notations
0
votes
1
answer
2
What is the recurrence for T(n)=2T(n/4)+sqrt(n) using the Master Theorem
How do I apply the master theorem in the above recurrence? Please give details about which case and on hiow to solve the asymptotic analysis...
lucasbbs
asked
in
Algorithms
Feb 28
by
lucasbbs
500
views
master-theorem
algorithms
recurrence-relation
0
votes
1
answer
3
Master Theorm
which formula to use in master theorm
flash12
asked
in
Algorithms
Sep 26, 2021
by
flash12
174
views
algorithms
master-theorem
recurrence-relation
0
votes
0
answers
4
NIELIT 2017 OCT Scientific Assistant A (IT) - Section B: 14
The running time of an algorithm $T(n),$ where $’n’$ is the input size , is given by $T(n) = 8T(n/2) + qn,$ if $n>1$ $= p,$ if $n = 1$ Where $p,q$ are constants. The order of this algorithm is $n^{2}$ $n^{n}$ $n^{3}$ $n$
Lakshman Patel RJIT
asked
in
Algorithms
Apr 1, 2020
by
Lakshman Patel RJIT
621
views
nielit2017oct-assistanta-it
algorithms
recurrence-relation
time-complexity
master-theorem
1
vote
1
answer
5
NIELIT 2017 OCT Scientific Assistant A (CS) - Section C: 4
The running time of an algorithm $T(n),$ where $’n’$ is the input size , is given by $T(n) = 8T(n/2) + qn,$ if $n>1$ $ = p,$ if $n = 1$ Where $p,q$ are constants. The order of this algorithm is $n^{2}$ $n^{n}$ $n^{3}$ $n$
Lakshman Patel RJIT
asked
in
Algorithms
Apr 1, 2020
by
Lakshman Patel RJIT
650
views
nielit2017oct-assistanta-cs
algorithms
recurrence-relation
time-complexity
master-theorem
3
votes
2
answers
6
ISRO2020-21
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
Satbir
asked
in
Algorithms
Jan 13, 2020
by
Satbir
1.6k
views
isro-2020
algorithms
master-theorem
easy
0
votes
1
answer
7
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?
lolster
asked
in
Algorithms
Jun 12, 2019
by
lolster
876
views
algorithms
master-theorem
time-complexity
asymptotic-notations
0
votes
0
answers
8
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})$.
akash.dinkar12
asked
in
Algorithms
Apr 5, 2019
by
akash.dinkar12
178
views
cormen
algorithms
recurrence-relation
master-theorem
descriptive
difficult
0
votes
0
answers
9
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$.
akash.dinkar12
asked
in
Algorithms
Apr 5, 2019
by
akash.dinkar12
147
views
cormen
algorithms
recurrence-relation
master-theorem
descriptive
difficult
0
votes
0
answers
10
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.
akash.dinkar12
asked
in
Algorithms
Apr 5, 2019
by
akash.dinkar12
201
views
cormen
algorithms
recurrence-relation
master-theorem
descriptive
difficult
0
votes
0
answers
11
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.
akash.dinkar12
asked
in
Algorithms
Apr 5, 2019
by
akash.dinkar12
165
views
cormen
algorithms
recurrence-relation
master-theorem
descriptive
0
votes
0
answers
12
Cormen Edition 3 Exercise 4.5 Question 3 (Page No. 97)
Use the master method to show that the solution to the binary-search recurrence $T(n)=T(n/2) + \Theta(1)$ is $T(n)=\Theta(lg\ n)$.
akash.dinkar12
asked
in
Algorithms
Apr 5, 2019
by
akash.dinkar12
139
views
cormen
algorithms
recurrence-relation
master-theorem
descriptive
0
votes
1
answer
13
Cormen Edition 3 Exercise 4.5 Question 2 (Page No. 97)
Professor Caesar wishes to develop a matrix-multiplication 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?
akash.dinkar12
asked
in
Algorithms
Apr 5, 2019
by
akash.dinkar12
831
views
cormen
algorithms
recurrence-relation
master-theorem
descriptive
0
votes
0
answers
14
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$
akash.dinkar12
asked
in
Algorithms
Apr 5, 2019
by
akash.dinkar12
472
views
cormen
algorithms
recurrence-relation
master-theorem
0
votes
0
answers
15
master theorem
what is master theorem for function like T(n) = aT(n-b) + f(n) where f(n) is not in the form of $n^k$
Hira Thakur
asked
in
Algorithms
Dec 13, 2018
by
Hira Thakur
427
views
master-theorem
0
votes
0
answers
16
Self Doubt
T(n)=4T(√n)+n How can we solve it using master theorem using subsitution and renaming.
jatin khachane 1
asked
in
Algorithms
Dec 1, 2018
by
jatin khachane 1
171
views
algorithms
master-theorem
self-doubt
0
votes
0
answers
17
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)
HeadShot
asked
in
Algorithms
Nov 27, 2018
by
HeadShot
248
views
master-theorem
0
votes
1
answer
18
madeeasy
how to apply masters theorem in this type of cases!????!
CHïntän ÞäTël
asked
in
Algorithms
Nov 19, 2018
by
CHïntän ÞäTël
129
views
algorithms
master-theorem
0
votes
1
answer
19
recurrence equation:
T(1) = 1 T(n) = 2T(n - 1) + n, n ≥ 2 evaluates to (a) 2n + 1 - n – 2 (b) 2n – n (c) 2n + 1 – 2n – 2 (d) 2n – n HOW TO EVALUATES USING MASTER THEOREM
altamash
asked
in
Algorithms
Nov 2, 2018
by
altamash
267
views
recurrence-relation
master-theorem
0
votes
0
answers
20
Master's theorem
Verma Ashish
asked
in
Algorithms
Oct 20, 2018
by
Verma Ashish
901
views
master-theorem
time-complexity
1
vote
6
answers
21
Can we solve the recurrence T(n) = T(n/2) + 2^n by masters theorem, if possible?
I was wondering whether the recurrence T(n) = T(n/2) + 2n could be solved by using master theorem, and what would be the way. I tried solving the recurrence but can't. There is no mention to it in CLRS book. Please help. Thanks in advance.
mohitrai0_0
asked
in
Algorithms
Sep 28, 2018
by
mohitrai0_0
11.1k
views
recurrence-relation
algorithms
master-theorem
time-complexity
asymptotic-notations
0
votes
2
answers
22
Self doubt
How to solve the given recurrence relation using master's theorem? T(n)=T(${n^{1/2}}$)+n
Verma Ashish
asked
in
Algorithms
Sep 19, 2018
by
Verma Ashish
377
views
algorithms
recurrence-relation
master-theorem
0
votes
2
answers
23
Analysis of the algorithms
T(n) = 3T( n/3 ) + n/2 The answer to the above question says that case 2 of masters theorem is applied here. How is it so?
sahil_malik
asked
in
Algorithms
Sep 11, 2018
by
sahil_malik
182
views
algorithms
recurrence-relation
master-theorem
0
votes
1
answer
24
Time complexity
T(n)=T(n-1)+O(n) Can we apply master's theorem here ??
Rajucse
asked
in
Algorithms
Aug 21, 2018
by
Rajucse
183
views
recurrence-relation
master-theorem
0
votes
0
answers
25
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?
pradeepchaudhary
asked
in
Algorithms
Aug 20, 2018
by
pradeepchaudhary
683
views
algorithms
recurrence-relation
time-complexity
master-theorem
1
vote
2
answers
26
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
manvi_agarwal
asked
in
Algorithms
Aug 11, 2018
by
manvi_agarwal
1.4k
views
made-easy-test-series
recurrence-relation
master-theorem
0
votes
2
answers
27
masters theorem
Solution using back substitution method T(n) = 2T(n/2) + nlogn ? detailed solution please. ans is nlognlogn or n(logn)^2
manvi_agarwal
asked
in
Algorithms
Aug 10, 2018
by
manvi_agarwal
571
views
time-complexity
algorithms
master-theorem
asymptotic-notations
recurrence-relation
0
votes
0
answers
28
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)=?
hitendra singh
asked
in
Algorithms
Aug 8, 2018
by
hitendra singh
368
views
algorithms
master-theorem
0
votes
1
answer
29
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.
Rahul Ranjan 1
asked
in
Algorithms
Aug 6, 2018
by
Rahul Ranjan 1
1.1k
views
master-theorem
time-complexity
algorithms
asymptotic-notations
recurrence-relation
0
votes
0
answers
30
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
Sandy Sharma
asked
in
Algorithms
Aug 1, 2018
by
Sandy Sharma
606
views
algorithms
master-theorem
Page:
1
2
3
4
next »
Subscribe to GATE CSE 2023 Test Series
Subscribe to GO Classes for GATE CSE 2023
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
Aptitude Overflow Book
Participate in Machine Learning benchmarking
GATE Overflow Tikz Templates
UPSC One Time Registration OTR Online Form 2022
DRDO CEPTAM 10 Online Form 2022
Subjects
All categories
General Aptitude
(2.4k)
Engineering Mathematics
(8.9k)
Digital Logic
(3.2k)
Programming and DS
(5.7k)
Algorithms
(4.5k)
Theory of Computation
(6.5k)
Compiler Design
(2.2k)
Operating System
(4.8k)
Databases
(4.4k)
CO and Architecture
(3.6k)
Computer Networks
(4.4k)
Non GATE
(1.2k)
Others
(2.5k)
Admissions
(644)
Exam Queries
(838)
Tier 1 Placement Questions
(17)
Job Queries
(72)
Projects
(9)
Unknown Category
(851)
Recent questions tagged master-theorem
Recent Blog Comments
Sir some test due date passed 1-2 months ago pls...
@lalitver10 There is no restriction in doing...
@GateOverflow04 link fixed now.
@Arjun @Deepak Sir, In Test Schedule google...
sir is this for gate? it has way more questions...