The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
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 recurrenceeqation
0
votes
0
answers
1
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
(
39k
points)

9
views
cormen
algorithms
recurrenceeqation
mastertheorem
descriptive
difficult
0
votes
0
answers
2
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
(
39k
points)

7
views
cormen
algorithms
recurrenceeqation
mastertheorem
descriptive
difficult
0
votes
0
answers
3
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
(
39k
points)

9
views
cormen
algorithms
recurrenceeqation
mastertheorem
descriptive
difficult
0
votes
0
answers
4
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
(
39k
points)

13
views
cormen
algorithms
recurrenceeqation
mastertheorem
descriptive
0
votes
0
answers
5
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
(
39k
points)

9
views
cormen
algorithms
recurrenceeqation
mastertheorem
descriptive
0
votes
0
answers
6
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
(
39k
points)

9
views
cormen
algorithms
recurrenceeqation
mastertheorem
descriptive
0
votes
0
answers
7
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
(
39k
points)

7
views
cormen
algorithms
recurrenceeqation
mastertheorem
0
votes
0
answers
8
Cormen Edition 3 Exercise 4.4 Question 9 (Page No. 93)
Use a recursion tree to give an asymptotically tight solution to the recurrence $T(n)=T(\alpha n) +T((1\alpha)n) +cn$,where $\alpha$ is a constant in the range $0<\alpha<1$ and $c>0$ is also constant.
asked
Apr 5
in
Algorithms
by
akash.dinkar12
Boss
(
39k
points)

6
views
cormen
algorithms
recurrenceeqation
descriptive
0
votes
0
answers
9
Cormen Edition 3 Exercise 4.4 Question 8 (Page No. 93)
Use a recursion tree to give an asymptotically tight solution to the recurrence $T(n) =T(na)+T(a)+cn$, where $a\geq 1$ and $c >0$ are constants.
asked
Apr 5
in
Algorithms
by
akash.dinkar12
Boss
(
39k
points)

7
views
cormen
algorithms
recurrenceeqation
descriptive
0
votes
0
answers
10
Cormen Edition 3 Exercise 4.4 Question 7 (Page No. 93)
Draw the recursion tree for $T(n)=4T(\lfloor n/2\rfloor) +cn$, where $c$ is a constant,and provide a tight asymptotic bound on its solution. Verify your bound by the substitution method.
asked
Apr 5
in
Algorithms
by
akash.dinkar12
Boss
(
39k
points)

3
views
cormen
algorithms
recurrenceeqation
descriptive
0
votes
0
answers
11
Cormen Edition 3 Exercise 4.4 Question 6 (Page No. 93)
Argue that the solution to the recurrence $T(n)=T(n/3)+T(2n/3)+cn$,where $c$ is a constant, is $\Omega(n\lg n)$ by appealing to a recursion tree.
asked
Apr 5
in
Algorithms
by
akash.dinkar12
Boss
(
39k
points)

5
views
cormen
algorithms
recurrenceeqation
descriptive
0
votes
0
answers
12
Cormen Edition 3 Exercise 4.4 Question 5 (Page No. 93)
Use a recursion tree to determine a good asymptotic upper bound on the recurrence $T(n)=T(n1)+T(n2) +n$.Use the substitution method to verify your answer.
asked
Apr 5
in
Algorithms
by
akash.dinkar12
Boss
(
39k
points)

4
views
cormen
algorithms
recurrenceeqation
descriptive
0
votes
0
answers
13
Cormen Edition 3 Exercise 4.4 Question 4 (Page No. 93)
Use a recursion tree to determine a good asymptotic upper bound on the recurrence $T(n) =2T(n1) + 1$.Use the substitution method to verify your answer.
asked
Apr 5
in
Algorithms
by
akash.dinkar12
Boss
(
39k
points)

4
views
cormen
algorithms
recurrenceeqation
descriptive
0
votes
0
answers
14
Cormen Edition 3 Exercise 4.4 Question 3 (Page No. 93)
Use a recursion tree to determine a good asymptotic upper bound on the recurrence $T(n)=4T(n/2 +2)+n$.Use the substitution method to verify your answer.
asked
Apr 5
in
Algorithms
by
akash.dinkar12
Boss
(
39k
points)

8
views
cormen
algorithms
recurrenceeqation
descriptive
0
votes
0
answers
15
Cormen Edition 3 Exercise 4.4 Question 2 (Page No. 92)
Use a recursion tree to determine a good asymptotic upper bound on the recurrence $T(n)=T(n/2)+n^2$.Use the substitution method to verify your answer
asked
Apr 5
in
Algorithms
by
akash.dinkar12
Boss
(
39k
points)

8
views
cormen
algorithms
recurrenceeqation
descriptive
0
votes
0
answers
16
Cormen Edition 3 Exercise 4.4 Question 1 (Page No. 92)
Use a recursion tree to determine a good asymptotic upper bound on the recurrence $T(n)=3T(\lfloor n/2 \rfloor) + n$. Use the substitution method to verify your answer.
asked
Apr 5
in
Algorithms
by
akash.dinkar12
Boss
(
39k
points)

6
views
cormen
algorithms
recurrenceeqation
descriptive
0
votes
0
answers
17
Cormen Edition 3 Exercise 4.3 Question 9 (Page No. 88)
Solve the recurrence $T(n)=3T(\sqrt n) +log\ n$ by making a change of variables.Your solution should be asymptotically tight. Do not worry about whether values are integral.
asked
Apr 5
in
Algorithms
by
akash.dinkar12
Boss
(
39k
points)

7
views
cormen
algorithms
recurrenceeqation
descriptive
0
votes
0
answers
18
Cormen Edition 3 Exercise 4.3 Question 8 (Page No. 87)
Using the master method, you can show that the solution to the recurrence $T(n) = 4T(n/2) +n^2$ is $T(n) = \Theta(n^2)$.Show that a substitution proof with the assumption $T(n) \leq cn^2$ fails. Then show how to subtract off a lowerorder term to make a substitution proof work.
asked
Apr 5
in
Algorithms
by
akash.dinkar12
Boss
(
39k
points)

9
views
cormen
algorithms
recurrenceeqation
descriptive
0
votes
0
answers
19
Cormen Edition 3 Exercise 4.3 Question 7 (Page No. 87)
Using the master method, you can show that the solution to the recurrence $T(n) = 4T(n/3) +n$ is $T(n) = O(n^{log_34})$.Show that a substitution proof with the assumption $T(n) \leq cn^{log_34}$ fails. Then show how to subtract off a lowerorder term to make a substitution proof work.
asked
Apr 5
in
Algorithms
by
akash.dinkar12
Boss
(
39k
points)

9
views
cormen
algorithms
recurrenceeqation
descriptive
0
votes
0
answers
20
Cormen Edition 3 Exercise 4.3 Question 6 (Page No. 87)
Show that the solution to $T(n) =T(\lfloor n/2 \rfloor+ 17) + n$ is $O(n\ log\ n)$
asked
Apr 5
in
Algorithms
by
akash.dinkar12
Boss
(
39k
points)

7
views
cormen
algorithms
recurrenceeqation
descriptive
0
votes
0
answers
21
Cormen Edition 3 Exercise 4.3 Question 3 (Page No. 87)
We saw that the solution of $T(n) = T(\lceil n/2 \rceil) + n$ is $O(lg\ n)$. Show that the solution of this recurrence is also $\Omega(n\ lg\ n)$. Conclude that the solution is $\Theta(n\log \ n)$.
asked
Apr 5
in
Algorithms
by
akash.dinkar12
Boss
(
39k
points)

10
views
cormen
algorithms
recurrenceeqation
descriptive
0
votes
0
answers
22
Cormen Edition 3 Exercise 4.3 Question 2 (Page No. 87)
Show that the solution of $T(n) = T(\lceil n/2\rceil) + 1$ is $O$(lg$ $n)$.
asked
Apr 5
in
Algorithms
by
akash.dinkar12
Boss
(
39k
points)

5
views
cormen
algorithms
recurrenceeqation
descriptive
0
votes
0
answers
23
Cormen Edition 3 Exercise 4.3 Question 1 (Page No. 87)
Show that the solution of $T(n) = T(n1)+ n$ is $O(n^2)$
asked
Apr 5
in
Algorithms
by
akash.dinkar12
Boss
(
39k
points)

7
views
cormen
algorithms
recurrenceeqation
descriptive
0
votes
1
answer
24
Recurrence relation and Time Complexity
What is the time complexity of the following recurrence relation and step to derive the same $T(n) = T(\sqrt{n}) + log(logn)$
asked
Jan 20
in
Algorithms
by
VikramRB
(
267
points)

107
views
timecomplexity
algorithms
recurrence
recurrenceeqation
0
votes
1
answer
25
Ace Test Series 2019: Discrete Maths  Recurrence Relation
asked
Jan 17
in
Linear Algebra
by
Rajesh Panwar
Junior
(
601
points)

64
views
acetestseries
discretemathematics
recurrenceeqation
0
votes
0
answers
26
Recurrence Relation for Array
A two dimensional array is stored in column major form in memory if the elements are stored in the following sequence ... calculated as the column number of the element we are looking for summing with the $row \times column$ number of elements. How does the above recurrence relation work?
asked
Jan 7
in
DS
by
kauray
(
321
points)

66
views
recurrence
recurrenceeqation
arrays
linearalgebra
operatingsystem
0
votes
0
answers
27
Ace Test Series: Discrete Maths  Recurrence Relation
asked
Jan 6
in
Combinatory
by
Sinchit
(
49
points)

28
views
acetestseries
discretemathematics
recurrenceeqation
0
votes
0
answers
28
Recurrence relation
T(n) = T(n/4) + T(3n/4) + n How to solve these type of problems? Can I solve this using master theorm by considering X = T(3N/4) +N THEN T(N) = T(N/4) +X CAN WE SOLVE LIKE THIS? PLEASE HELP
asked
Jan 4
in
Algorithms
by
Mayankprakash
Active
(
1.1k
points)

112
views
recurrenceeqation
timecomplexity
recurrence
algorithms
0
votes
1
answer
29
Solve the recurrence $T(n) = 2 T \left ( \sqrt n \right ) + n$
asked
Dec 21, 2018
in
Algorithms
by
`JEET
Active
(
3.4k
points)

181
views
recurrenceeqation
0
votes
0
answers
30
ace academy test series
Please explain in some detail.
asked
Nov 23, 2018
in
Combinatory
by
amitqy
Active
(
1.9k
points)

31
views
recurrenceeqation
discretemathematics
Page:
1
2
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
How to prepare for IISC Interdisciplinary Mathematical Sciences Interview
GO Hardcopy for GATE 2020
How to prepare for BARC interview
IIIT H
Tips for COAP2019
Follow @csegate
Recent questions tagged recurrenceeqation
Recent Blog Comments
What is the cutoff for M.Tech AI at IISc?
Yup. Hard copy contains a unique QR code for...
Lol. I got left out of IIT Kanpur GATE cutoff by...
Don't worry brother... i hope fate is also get...
50,049
questions
53,194
answers
184,527
comments
70,400
users