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, 2019
in
Algorithms
by
Jyoti Kumari97
(
187
points)

789
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, 2019
in
Algorithms
by
srestha
Veteran
(
119k
points)

79
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, 2019
in
Combinatory
by
aditi19
Loyal
(
5.2k
points)

67
views
relations
recurrence
recurrenceeqation
discretemathematics
combinational
0
votes
1
answer
4
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, 2019
in
Algorithms
by
srestha
Veteran
(
119k
points)

158
views
algorithms
timecomplexity
recurrenceeqation
0
votes
0
answers
5
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.5k
points)

22
views
cormen
algorithms
recurrenceeqation
mastertheorem
descriptive
difficult
0
votes
0
answers
6
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.5k
points)

17
views
cormen
algorithms
recurrenceeqation
mastertheorem
descriptive
difficult
0
votes
0
answers
7
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.5k
points)

29
views
cormen
algorithms
recurrenceeqation
mastertheorem
descriptive
difficult
0
votes
0
answers
8
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.5k
points)

23
views
cormen
algorithms
recurrenceeqation
mastertheorem
descriptive
0
votes
0
answers
9
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.5k
points)

18
views
cormen
algorithms
recurrenceeqation
mastertheorem
descriptive
0
votes
0
answers
10
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.5k
points)

27
views
cormen
algorithms
recurrenceeqation
mastertheorem
descriptive
0
votes
0
answers
11
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.5k
points)

26
views
cormen
algorithms
recurrenceeqation
mastertheorem
0
votes
0
answers
12
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.5k
points)

12
views
cormen
algorithms
recurrenceeqation
descriptive
0
votes
0
answers
13
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.5k
points)

13
views
cormen
algorithms
recurrenceeqation
descriptive
0
votes
0
answers
14
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.5k
points)

8
views
cormen
algorithms
recurrenceeqation
descriptive
0
votes
0
answers
15
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.5k
points)

9
views
cormen
algorithms
recurrenceeqation
descriptive
0
votes
0
answers
16
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.5k
points)

10
views
cormen
algorithms
recurrenceeqation
descriptive
0
votes
0
answers
17
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.5k
points)

7
views
cormen
algorithms
recurrenceeqation
descriptive
0
votes
0
answers
18
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.5k
points)

15
views
cormen
algorithms
recurrenceeqation
descriptive
0
votes
1
answer
19
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.5k
points)

21
views
cormen
algorithms
recurrenceeqation
descriptive
0
votes
0
answers
20
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.5k
points)

11
views
cormen
algorithms
recurrenceeqation
descriptive
0
votes
0
answers
21
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.5k
points)

18
views
cormen
algorithms
recurrenceeqation
descriptive
0
votes
0
answers
22
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.5k
points)

13
views
cormen
algorithms
recurrenceeqation
descriptive
0
votes
0
answers
23
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.5k
points)

14
views
cormen
algorithms
recurrenceeqation
descriptive
0
votes
0
answers
24
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.5k
points)

11
views
cormen
algorithms
recurrenceeqation
descriptive
0
votes
0
answers
25
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.5k
points)

14
views
cormen
algorithms
recurrenceeqation
descriptive
0
votes
0
answers
26
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.5k
points)

13
views
cormen
algorithms
recurrenceeqation
descriptive
0
votes
0
answers
27
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.5k
points)

12
views
cormen
algorithms
recurrenceeqation
descriptive
0
votes
1
answer
28
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, 2019
in
Algorithms
by
VikramRB
(
239
points)

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

105
views
acetestseries
discretemathematics
recurrenceeqation
0
votes
0
answers
30
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, 2019
in
DS
by
kauray
(
215
points)

105
views
recurrence
recurrenceeqation
arrays
linearalgebra
operatingsystem
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
ISRO CSE 2020 PAPER ANALYSE
BARC OCES/DGFS 2020
ISI CMI PDF by GATE Overflow
Calculus Important Points
Management Trainee Recruitment COAL INDIA 2020
Follow @csegate
Recent questions tagged recurrenceeqation
Recent Blog Comments
@nsaisirisha Yes they will give marks only...
When will the results be declared based on...
For the questions with two answers as per the...
@MiNiPanda Congrax mate for this success !
Mostly authentic links, it can be Stackoverflow,...
50,737
questions
57,333
answers
198,441
comments
105,198
users