The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
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 26, 2019
in
Algorithms
by
Jyoti Kumari97

2.3k
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 20, 2019
in
Algorithms
by
srestha

105
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

102
views
relations
recurrence
recurrenceeqation
discretemathematics
combinational
0
votes
3
answers
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

235
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 6, 2019
in
Algorithms
by
akash.dinkar12

42
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 6, 2019
in
Algorithms
by
akash.dinkar12

32
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

40
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

37
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

28
views
cormen
algorithms
recurrenceeqation
mastertheorem
descriptive
0
votes
1
answer
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

64
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

61
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

20
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

22
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

18
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

19
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(n/2) +n$.Use the substitution method to verify your answer.
asked
Apr 5, 2019
in
Algorithms
by
akash.dinkar12

47
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

14
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

27
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

43
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

21
views
cormen
algorithms
recurrenceeqation
descriptive
0
votes
1
answer
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

45
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

23
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

20
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

18
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

24
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

20
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

22
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 21, 2019
in
Algorithms
by
VikramRB

313
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

134
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

154
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
IISc CDS Interview Experience, 2020
IITD MS CSE (Systems) Experience
IIT Bombay M.Tech. (RA)  Interview Experience
Interview Experience for MS(R)IIT Delhi (School of Information Technology)
PGEE 2020 (CSE) Experience
Subjects
All categories
General Aptitude
(2k)
Engineering Mathematics
(8.3k)
Digital Logic
(2.9k)
Programming and DS
(5k)
Algorithms
(4.4k)
Theory of Computation
(6.2k)
Compiler Design
(2.2k)
Operating System
(4.6k)
Databases
(4.2k)
CO and Architecture
(3.4k)
Computer Networks
(4.2k)
Non GATE
(1.2k)
Others
(1.5k)
Admissions
(595)
Exam Queries
(562)
Tier 1 Placement Questions
(23)
Job Queries
(71)
Projects
(19)
Unknown Category
(1k)
Recent questions tagged recurrenceeqation
Recent Blog Comments
After the written exam and at the time of...
Q1. I don't know any trick or method, I usually...
Yeah, Now it's on.
Can you check now?
Even I filled NIELIT form which had similar...
Network Sites
GO Mechanical
GO Electrical
GO Electronics
GO Civil
CSE Doubts
52,375
questions
60,580
answers
201,986
comments
95,396
users