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
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
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)

413
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
(
116k
points)

71
views
discretemathematics
recurrenceeqation
algorithms
+1
vote
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
(
5k
points)

55
views
relations
recurrence
recurrenceeqation
discretemathematics
combinational
+2
votes
1
answer
4
ISI2018PCBCS2
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.7k
points)

44
views
isi2018pcbcs
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
(
116k
points)

139
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.7k
points)

20
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.7k
points)

15
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.7k
points)

24
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.7k
points)

19
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.7k
points)

16
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.7k
points)

18
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.7k
points)

20
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.7k
points)

11
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.7k
points)

13
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.7k
points)

7
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.7k
points)

8
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.7k
points)

9
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.7k
points)

5
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.7k
points)

13
views
cormen
algorithms
recurrenceeqation
descriptive
0
votes
1
answer
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.7k
points)

17
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.7k
points)

10
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.7k
points)

15
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.7k
points)

10
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.7k
points)

13
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.7k
points)

9
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.7k
points)

12
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.7k
points)

8
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.7k
points)

10
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)

189
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
(
787
points)

94
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
IIITH: Winter Research Admissions 2019 (For Spring 2020)
TIFR and JEST exam
Minimal Deterministic Finite Automata
To be aware of fake GATE test series
Standard Book Exercise Questions for Computer Science
Follow @csegate
Recent questions tagged recurrenceeqation
Recent Blog Comments
Favorite is not working for blogs.. In favorites...
Favourite option does work. But list options...
Blog favorite button doesnt work?
@Arjun Sir can we have an option to save such...
Thanks Sir
50,666
questions
56,164
answers
193,781
comments
93,871
users