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
0
answers
1
How to solve the following recurrence relation? I get confused when decimals are used in the expression.
rexritz
asked
in
Algorithms
Aug 13, 2023
by
rexritz
291
views
recurrence-relation
master-theorem
1
vote
1
answer
2
how to solve T(n)=4T(√n)+3^5n with master theorem
how do i apply master theorem to this?
mdboi
asked
in
Algorithms
Oct 29, 2022
by
mdboi
1.0k
views
algorithms
recurrence-relation
master-theorem
asymptotic-notation
1
vote
2
answers
3
how to solve T(n)=2T(n/2)−n^3n with master theorem
how do i apply master theorem to this? T(n)=2T(n/2)−n^3n
mdboi
asked
in
Algorithms
Oct 28, 2022
by
mdboi
730
views
algorithms
master-theorem
recurrence-relation
asymptotic-notation
1
vote
1
answer
4
𝑇(𝑛)=16𝑇(𝑛/4)+5𝑛^3 using the master theorem
how do i apply master theorem to this? 𝑇(𝑛)=16𝑇(𝑛/4)+5𝑛^3
mdboi
asked
in
Algorithms
Oct 28, 2022
by
mdboi
709
views
algorithms
master-theorem
recurrence-relation
asymptotic-notation
time-complexity
1
vote
1
answer
5
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, 2022
by
ItzDc
2.8k
views
algorithms
recurrence-relation
master-theorem
0
votes
1
answer
6
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, 2022
by
lucasbbs
6.5k
views
master-theorem
algorithms
recurrence-relation
0
votes
1
answer
7
Master Theorm
which formula to use in master theorm
flash12
asked
in
Algorithms
Sep 26, 2021
by
flash12
316
views
algorithms
master-theorem
recurrence-relation
0
votes
0
answers
8
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 Bhaiya
asked
in
Algorithms
Apr 1, 2020
by
Lakshman Bhaiya
850
views
nielit2017oct-assistanta-it
algorithms
recurrence-relation
time-complexity
master-theorem
1
vote
1
answer
9
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 Bhaiya
asked
in
Algorithms
Apr 1, 2020
by
Lakshman Bhaiya
1.2k
views
nielit2017oct-assistanta-cs
algorithms
recurrence-relation
time-complexity
master-theorem
3
votes
2
answers
10
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
2.7k
views
isro-2020
algorithms
master-theorem
easy
0
votes
1
answer
11
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
1.3k
views
algorithms
master-theorem
time-complexity
asymptotic-notation
0
votes
0
answers
12
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
278
views
cormen
algorithms
recurrence-relation
master-theorem
descriptive
difficult
0
votes
0
answers
13
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
213
views
cormen
algorithms
recurrence-relation
master-theorem
descriptive
difficult
0
votes
0
answers
14
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
323
views
cormen
algorithms
recurrence-relation
master-theorem
descriptive
difficult
0
votes
1
answer
15
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
275
views
cormen
algorithms
recurrence-relation
master-theorem
descriptive
0
votes
0
answers
16
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
244
views
cormen
algorithms
recurrence-relation
master-theorem
descriptive
0
votes
1
answer
17
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
1.2k
views
cormen
algorithms
recurrence-relation
master-theorem
descriptive
0
votes
0
answers
18
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
651
views
cormen
algorithms
recurrence-relation
master-theorem
0
votes
0
answers
19
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
717
views
master-theorem
0
votes
0
answers
20
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
289
views
algorithms
master-theorem
self-doubt
0
votes
0
answers
21
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
347
views
master-theorem
0
votes
1
answer
22
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
284
views
algorithms
master-theorem
0
votes
1
answer
23
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
388
views
recurrence-relation
master-theorem
0
votes
0
answers
24
Master's theorem
Verma Ashish
asked
in
Algorithms
Oct 20, 2018
by
Verma Ashish
1.6k
views
master-theorem
time-complexity
1
vote
6
answers
25
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
18.9k
views
recurrence-relation
algorithms
master-theorem
time-complexity
asymptotic-notation
0
votes
2
answers
26
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
706
views
algorithms
recurrence-relation
master-theorem
0
votes
2
answers
27
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
297
views
algorithms
recurrence-relation
master-theorem
0
votes
1
answer
28
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
358
views
recurrence-relation
master-theorem
0
votes
0
answers
29
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
880
views
algorithms
recurrence-relation
time-complexity
master-theorem
Page:
1
2
3
4
next »
Subscribe to GATE CSE 2024 Test Series
Subscribe to GO Classes for GATE CSE 2024
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
Post GATE 2024 Guidance [Counseling tips and resources]
GATE CSE 2024 Result Responses
[Project Contest] Pytorch backend support for MLCommons Cpp Inference implementation
Participating in MLCommons Inference v4.0 submission (deadline is February 23 12pm IST)
IIITH PGEE 2024 Test Series by GO Classes
Subjects
All categories
General Aptitude
(3.5k)
Engineering Mathematics
(10.4k)
Digital Logic
(3.6k)
Programming and DS
(6.2k)
Algorithms
(4.8k)
Theory of Computation
(6.9k)
Compiler Design
(2.5k)
Operating System
(5.2k)
Databases
(4.8k)
CO and Architecture
(4.0k)
Computer Networks
(4.9k)
Artificial Intelligence
(79)
Machine Learning
(48)
Data Mining and Warehousing
(25)
Non GATE
(1.4k)
Others
(2.7k)
Admissions
(683)
Exam Queries
(1.6k)
Tier 1 Placement Questions
(17)
Job Queries
(80)
Projects
(11)
Unknown Category
(870)
64.3k
questions
77.9k
answers
243k
comments
79.7k
users
Recent questions tagged master-theorem
Recent Blog Comments
Hlo I'm Rupesh I got AIR 3485 in gate CS and AIR...
@Ajay Sasank here is the direct link...
Thank you for the post didi My GATE 2023 & 2024...
I Hope it helps 😊
Today's best post I seen thank you for motivation