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
All Activity
Questions
Unanswered
Tags
Categories
Users
Ask a Question
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
+1
vote
3
answers
1
Made easy Workbook 2020
Question: $T(1)=1$ $T(n) = 2 T(n  1) + n$ evaluates to? Can anyone solve it by substitution method? Given answer $T(n) = 2^{n+1}  (n+2)$ How?
asked
May 25
in
Algorithms
by
Jyoti Kumari97
(
181
points)

179
views
timecomplexity
algorithms
recurrenceeqation
+1
vote
0
answers
2
Recurrence RelationSelf Doubt(Discrete Math+Algo)
Let $A(n)$ denotes the number of $n$ bit binary strings which have no pair of consecutive $1’s.$ what will be recurrence relation for it and what will be it’s Time Complexity??
asked
May 19
in
Algorithms
by
srestha
Veteran
(
113k
points)

62
views
discretemathematics
recurrenceeqation
algorithms
0
votes
1
answer
3
Recurrence Relation SelfDoubt
What will be solution of recurrence relation if roots are like this: r1=2, r2=2, r3=2, r4=2 is this the case of repetitive roots?
asked
May 14
in
Combinatory
by
aditi19
Active
(
4.1k
points)

47
views
relations
recurrence
recurrenceeqation
discretemathematics
combinational
0
votes
1
answer
4
ISI2018PCBB2
You can climb up a staircase of $n$ stairs by taking steps of one or two stairs at a time. Formulate a recurrence relation for counting $a_n$, the number of distinct ways in which you can climb up the staircase. Mention the boundary conditions for your recurrence relation. Find a closed form expression for $a_n$ by solving your recurrence.
asked
May 12
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

35
views
isi2018pcbb
algorithms
recurrenceeqation
descriptive
0
votes
1
answer
5
Made Easy Test Series:AlgorithmRecurrence Relation
What is the solution of recurrence relation $T\left ( n \right )=T\left ( n1 \right )+n$
asked
May 10
in
Algorithms
by
srestha
Veteran
(
113k
points)

110
views
algorithms
timecomplexity
recurrenceeqation
0
votes
0
answers
6
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
(
41.3k
points)

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

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

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

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

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

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

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

8
views
cormen
algorithms
recurrenceeqation
descriptive
0
votes
0
answers
14
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
(
41.3k
points)

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

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

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

8
views
cormen
algorithms
recurrenceeqation
descriptive
0
votes
0
answers
18
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
(
41.3k
points)

4
views
cormen
algorithms
recurrenceeqation
descriptive
0
votes
0
answers
19
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
(
41.3k
points)

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

10
views
cormen
algorithms
recurrenceeqation
descriptive
0
votes
0
answers
21
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
(
41.3k
points)

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

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

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

10
views
cormen
algorithms
recurrenceeqation
descriptive
0
votes
0
answers
25
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
(
41.3k
points)

8
views
cormen
algorithms
recurrenceeqation
descriptive
0
votes
0
answers
26
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
(
41.3k
points)

11
views
cormen
algorithms
recurrenceeqation
descriptive
0
votes
0
answers
27
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
(
41.3k
points)

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

9
views
cormen
algorithms
recurrenceeqation
descriptive
0
votes
1
answer
29
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
(
239
points)

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

81
views
acetestseries
discretemathematics
recurrenceeqation
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
ISI MTECH CS 2019 INTERVIEW EXPERIENCE
IIT HYDERABAD MTECH TA INTERVIEW EXPERIENCE
How to prepare for GATE with a fulltime job??
Interview Experience at IISc
All subject Gate notes from Standard Books!!
Follow @csegate
Recent questions tagged recurrenceeqation
Recent Blog Comments
Refund time depends on the payment mode ...
@Arjun Sir , when can i expect my refund in the...
This book is returned you can enable a pay now...
@Pranavcool The book stocks are over and no one...
@Lokesh Thats unfortunate. I have refunded you....
49,830
questions
54,807
answers
189,530
comments
80,840
users