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
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 recurrence
Master Theorem
Extended Master Theorem
Even more extension
0
votes
0
answers
1
Cormen Edition 3 Exercise 7.4 Question 1 (Page No. 184)
Show that in the recurrence $T(n)=\max_{0<q\leq n1} (T(q)+T(nq1))+\Theta(n)$ $T(n)=\Omega(n^2)$
asked
Jun 28
in
Algorithms
by
akash.dinkar12
Boss
(
41.7k
points)

21
views
cormen
algorithms
recurrence
descriptive
0
votes
0
answers
2
Cormen Edition 3 Exercise 7.2 Question 1 (Page No. 178)
Use the substitution method to prove that the recurrence $T(n)=T(n1) + \Theta(n)$ has the solution $T(n) =\Theta(n^2)$.
asked
Jun 27
in
Algorithms
by
akash.dinkar12
Boss
(
41.7k
points)

11
views
cormen
algorithms
recurrence
descriptive
0
votes
1
answer
3
Cormen Edition 3 Exercise 2.3 Question 3 (Page No. 39)
Use mathematical induction to show that when $n$ is an exact power of $2$, the solution of the recurrence $T(n) = \begin{cases} 2 \text{, if n=2, } \\2T(n/2)+n \text{, if n=$2^k$,for k >1} \end{cases}$ is $T(n) = n\ lg\ n$.
asked
Jun 26
in
Algorithms
by
akash.dinkar12
Boss
(
41.7k
points)

41
views
cormen
algorithms
recurrence
timecomplexity
descriptive
0
votes
0
answers
4
#ACE ACADEMY BOOKLET QUESTION
The solution of $\sqrt{a_n} – 2\sqrt{a_{n1}} + \sqrt{a_{n2}} = 0$ where $a_0 = 1$ and $a_1 = 2$ is ${\Big[\frac{2^{n+1} + (1)^n}{3}\Big]}^2$ $(n+1)^2$ $(n1)^3$ $(n1)^2$
asked
Jun 5
in
Combinatory
by
`JEET
Loyal
(
8.2k
points)

108
views
discretemathematics
permutationandcombination
recurrence
#recurrencerelations
+1
vote
0
answers
5
GATE1999
Consider the following algorithms. Assume, procedure $A$ and procedure $B$ take $O(1)$ and $O(1/n)$ unit of time respectively. Derive the time complexity of the algorithm in $O$ notation. algorithm what (n) begin if n = 1 then call A else begin what (n1); call B(n ... $c$ So complexity should be $O(1)$. But answer is $O(n)$.What I am doing wrong?
asked
Jun 4
in
Algorithms
by
kshitij
(
145
points)

118
views
algorithms
timecomplexity
recurrence
+1
vote
1
answer
6
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.9k
points)

52
views
relations
recurrence
recurrenceeqation
discretemathematics
combinational
0
votes
0
answers
7
Rosen 7e Exercise 8.2 Questionno26 page no525 Recurrence Relation
What is the general form of the particular solution guaranteed to exist of the linear nonhomogeneous recurrence relation $a_n$=$6a_{n1}$$12a_{n2}$+$8a_{n3}$+F(n) if F(n)=$n^2$ F(n)=$2^n$ F(n)=$n2^n$ F(n)=$(2)^n$ F(n)=$n^22^n$ F(n)=$n^3(2)^n$ F(n)=3
asked
May 14
in
Combinatory
by
aditi19
Active
(
4.9k
points)

44
views
kennethrosen
discretemathematics
#recurrencerelations
recurrence
0
votes
0
answers
8
Rosen 7e Exercise8.2 Question no23 page no525 Recurrence Relation
Consider the nonhomogeneous linear recurrence relation $a_n$=$3a_{n1}$+$2^n$ in the book solution is given $a_n$=$2^{n+1}$ but I’m getting $a_n$=$3^{n+1}2^{n+1}$
asked
May 13
in
Combinatory
by
aditi19
Active
(
4.9k
points)

30
views
kennethrosen
discretemathematics
#recurrencerelations
recurrence
0
votes
1
answer
9
Rosen 7e Recurrence Relation Exercise8.1 Question no25 page no511
How many bit sequences of length seven contain an even number of 0s? I'm trying to solve this using recurrence relation Is my approach correct? Let T(n) be the string having even number of 0s T(1)=1 {1} T(2)=2 {00, 11} T(3)=4 {001, ... add 0 to strings of length n1 having odd number of 0s T(n)=T(n1) Hence, we have T(n)=2T(n1)
asked
Apr 29
in
Combinatory
by
aditi19
Active
(
4.9k
points)

53
views
kennethrosen
discretemathematics
permutationandcombination
#recurrencerelations
recurrence
0
votes
1
answer
10
Rosen 7e Exercise8.1 Question no10 Page no511
Find a recurrence relation for the number of bit strings of length n that contain the string 01.
asked
Apr 28
in
Combinatory
by
aditi19
Active
(
4.9k
points)

49
views
kennethrosen
discretemathematics
permutationandcombination
#recurrencerelations
recurrence
0
votes
0
answers
11
Time complexity
Is this the correct way to solve ? Q) int algorithm(int n) { int sum =0;k,j; for (k=0;k<n/2;k++) for(j=0;j<10;j++) sum++; return 4*algorithm(n/2)*algorithm(n/2)+algorithm(n/2)*algorithm(n/2) }
asked
Mar 15
in
Algorithms
by
syncronizing
Junior
(
809
points)

143
views
timecomplexity
algorithms
recurrence
0
votes
1
answer
12
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)

177
views
timecomplexity
algorithms
recurrence
recurrenceeqation
0
votes
0
answers
13
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
(
209
points)

93
views
recurrence
recurrenceeqation
arrays
linearalgebra
operatingsystem
0
votes
1
answer
14
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
Junior
(
997
points)

177
views
recurrenceeqation
timecomplexity
recurrence
algorithms
+1
vote
0
answers
15
NonLeft recursive grammar of the below grammar.
Grammar. S → Aa  B A → Ac  Aad  bd  epsilon . .
asked
Jan 2
in
Compiler Design
by
susgir2
Active
(
1.5k
points)

78
views
compilerdesign
leftrecursion
grammar
parsing
recurrence
0
votes
0
answers
16
MadeEasy Full Length Test: Combinatory  Recurrence
What’s the trick to do it under 2 min here?
asked
Dec 31, 2018
in
Combinatory
by
shaz
(
359
points)

260
views
madeeasytestseries
#recurrencerelations
recurrence
0
votes
1
answer
17
time complexity
asked
Dec 30, 2018
in
Algorithms
by
Rahul_Rathod_
(
421
points)

68
views
timecomplexity
algorithms
asymptoticnotations
recurrence
+3
votes
1
answer
18
GO2019FLT148
Consider the following piece of pseudocode: A(n){ if(n==0) return 1; return A(√n) + B(n) + C(n) + D(n); } B(n){ if (n==0) return n; return B(n1); } C(n){ return A (√n); } D(n){ return n; } What is the time complexity in terms of Big $\Theta$ notation for the function call to procedure A? $\Theta(n)$ $\Theta(n \log n)$ $\Theta(n \log \log n)$ $\Theta(n^2 \log n)$
asked
Dec 27, 2018
in
Others
by
Ruturaj Mohanty
Active
(
2.5k
points)

255
views
go2019flt1
asymptoticnotations
recurrence
0
votes
1
answer
19
Testbook Test Series: Algorithms  Recurrence
…………………………..
asked
Dec 27, 2018
in
Algorithms
by
Magma
Boss
(
13.7k
points)

115
views
testbooktestseries
algorithms
recurrence
+1
vote
0
answers
20
https://gateoverflow.in/33989/howtosolvebelowrecurrencerelation
https://gateoverflow.in/33989/howtosolvebelowrecurrencerelation
asked
Dec 23, 2018
in
Combinatory
by
mitesh kumar
(
345
points)

47
views
recurrence
discretemathematics
+1
vote
2
answers
21
#discrete matmatics
recurrence relation 2a$_{n}=a_{n1}+2^{n}$ intial condtion a$_{0}$=1 value of a$_{100}$
asked
Dec 12, 2018
in
Combinatory
by
amit166
Junior
(
701
points)

63
views
recurrence
0
votes
0
answers
22
SELF DOUBT GENERATING FUNCTION
Difference between getting closed form of generating function and closed form of the given sequence ,pls someone explain with an example
asked
Dec 10, 2018
in
Combinatory
by
codingo1234
Junior
(
819
points)

42
views
generatingfunctions
recurrence
+1
vote
1
answer
23
How is the time Complexity of this problem O(n log log n)?
int A(int n){ for(i = 1; i < n; i++) for(j = 1; j < i; j *= 2) for(k = j; k >= 1; k /= 2) if(n = 0) return 1; else{ for(z = 0; z < n; z++){ // do something } } } How do find the complexity of this problem? The answer is supposed to be O(n log log n), but it maybe wrong.
asked
Nov 22, 2018
in
Algorithms
by
gmrishikumar
Active
(
1.9k
points)

514
views
algorithms
timecomplexity
recurrence
programminginc
+1
vote
1
answer
24
T(n) = sqrt(n) * T(sqrt(n)) + n
T(n) = sqrt(n) * T(sqrt(n)) + n Given solution is O(log log n). But my solution is O(n log log n). 'wolframalpha'' shows the answer same as mine. You can find the solution here. Can anyone confirm the solution and provide an explantion?
asked
Nov 22, 2018
in
Algorithms
by
gmrishikumar
Active
(
1.9k
points)

608
views
algorithms
recurrence
timecomplexity
recursion
0
votes
0
answers
25
recurrence relation
T(n)=5 T ($\frac{n}{2}$+16) + n2 please tell the solution as i m getting confused
asked
Nov 18, 2018
in
Algorithms
by
LavTheRawkstar
Active
(
3.7k
points)

129
views
relations
recurrence
algorithms
timecomplexity
recurrenceeqation
0
votes
0
answers
26
Time Complexity
How to solve the following recurrence relation? T(n) = T(n6) + n2 , n>7 T(n) = 1 , n<= 7
asked
Nov 17, 2018
in
Algorithms
by
garvit_vijai
(
257
points)

90
views
timecomplexity
asymptoticnotations
recurrence
algorithms
0
votes
1
answer
27
What is the value of T(n) for the given recurrence relation
T(n)=T(n/2)+2; T(1)=1 when n is power of 2 the correct expression for T(n) is: a) 2(logn+1) b) 2logn c)logn+1 d)2logn+1
asked
Nov 14, 2018
in
Algorithms
by
sripo
Active
(
2.3k
points)

132
views
recurrence
algorithms
timecomplexity
jest
0
votes
1
answer
28
test series  Testbook
Which of the following functions given by their recurrences grows the fastest asymptotically? $T(n) = 8T(n/4) + 100n^2$ $T(n) = 81T(n/9) + 10n^2$ $T(n) = 16T(n/4)+ 100(n \log n)^{1.99}$ $T(n) = 100T(n/100)+ n \log^2 n$
asked
Nov 13, 2018
in
Algorithms
by
Shubham Aggarwal
Active
(
1.8k
points)

146
views
asymptoticnotations
recurrence
0
votes
1
answer
29
Analysis of algorithms of recurrence relation
I want to learn to find time complexity of the recurrence relation of an algorithm. Please suggest some good links or any gatetoverflow imp questions links to look as examples . Thanks
asked
Oct 31, 2018
in
Algorithms
by
Mayankprakash
Junior
(
997
points)

88
views
algorithms
recurrenceeqation
recurrence
+1
vote
1
answer
30
Time Complexity
how to compute time complexity of this kind of recurrence relation T(n)=T(n/2)+T(n/4)+T(n/8)+n
asked
Oct 27, 2018
in
Algorithms
by
aditi19
Active
(
4.9k
points)

122
views
timecomplexity
algorithms
asymptoticnotations
recurrence
Page:
1
2
3
4
5
6
...
10
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
Standard Book Exercise Questions for Computer Science
Resource to Learn Graph Theory Interactively
Recruitment to the post of Scientist/Engineer 'SC' (Electronics, Mechanical and Computer Science)
Standard Videos for Calculus
Standard Videos for Linear Algebra
Follow @csegate
Recent questions tagged recurrence
Recent Blog Comments
Are the answers also present ?
@Arjun sir , Is there any page or something where...
@arjun sir but u called about providing the pdfs...
But anyhow I appreciate this. The questions of...
All these PYQ blogs and standard videos blogs...
50,407
questions
55,863
answers
192,661
comments
91,660
users