Register

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.
$T\left ( n \right )= 8T\left ( \frac{n}{2} \right )+\left ( n\cdot logn \right )^{2.99}$Also can $\mathcal{O}(n^{3})$ be an upper bound to above recurrence relation?
User Avatar
1 votes
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)
I can't figure out how to proceed and which case it's falling under after calculating h(n)
User Avatar
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...
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...
User Avatar
0 votes
1 answer
7
Master Theorm
which formula to use in master theorm
which formula to use in master theorm
User Avatar
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
The master theoremassumes the subproblems are unequal sizescan be used if the subproblems are of equal sizecannot be used for divide and conquer algorithmscannot be used ...
User Avatar
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?
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 Mas...
User Avatar
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.
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.
User Avatar
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)$.
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)$.
User Avatar
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$
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$
User Avatar
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$
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$
User Avatar
0 votes
0 answers
20
Self Doubt
T(n)=4T(√n)+n How can we solve it using master theorem using subsitution and renaming.
T(n)=4T(√n)+nHow can we solve it using master theorem using subsitution and renaming.
User Avatar
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)
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 nT(n) =...
User Avatar
0 votes
1 answer
22
madeeasy
how to apply masters theorem in this type of cases!????!
how to apply masters theorem in this type of cases!????!
User Avatar
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
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
User Avatar
0 votes
0 answers
24
Master's theorem
User Avatar
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
How to solve the given recurrence relation using master's theorem?T(n)=T(${n^{1/2}}$)+n
User Avatar
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?
T(n) = 3T( n/3 ) + n/2The answer to the above question says that case 2 of masters theorem is applied here. How is it so?
User Avatar
0 votes
1 answer
28
Time complexity
T(n)=T(n-1)+O(n) Can we apply master's theorem here ??
T(n)=T(n-1)+O(n)Can we apply master's theorem here ??
User Avatar
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?
T (n) = T (n/2) + 2nUsing Master's Method What is the Complexity Of This Recurrence Relation?Or Using AnyOther Method?
User Avatar
Page: