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
#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
Active
(
3.3k
points)

67
views
discretemathematics
permutationandcombination
recurrence
#recurrencerelations
+1
vote
0
answers
2
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
(
85
points)

90
views
algorithms
timecomplexity
recurrence
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
(
3.7k
points)

37
views
relations
recurrence
recurrenceeqation
discretemathematics
combinational
0
votes
0
answers
4
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
(
3.7k
points)

34
views
kennethrosen
discretemathematics
#recurrencerelations
recurrence
0
votes
0
answers
5
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
(
3.7k
points)

23
views
kennethrosen
discretemathematics
#recurrencerelations
recurrence
0
votes
0
answers
6
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
(
3.7k
points)

40
views
kennethrosen
discretemathematics
permutationandcombination
#recurrencerelations
recurrence
0
votes
1
answer
7
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
(
3.7k
points)

38
views
kennethrosen
discretemathematics
permutationandcombination
#recurrencerelations
recurrence
0
votes
0
answers
8
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
(
789
points)

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

145
views
timecomplexity
algorithms
recurrence
recurrenceeqation
0
votes
0
answers
10
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
(
197
points)

74
views
recurrence
recurrenceeqation
arrays
linearalgebra
operatingsystem
0
votes
1
answer
11
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
(
979
points)

148
views
recurrenceeqation
timecomplexity
recurrence
algorithms
+1
vote
0
answers
12
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.4k
points)

68
views
compilerdesign
leftrecursion
grammar
parsing
recurrence
0
votes
0
answers
13
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
(
337
points)

253
views
madeeasytestseries
#recurrencerelations
recurrence
0
votes
1
answer
14
time complexity
asked
Dec 30, 2018
in
Algorithms
by
Rahul_Rathod_
(
415
points)

46
views
timecomplexity
algorithms
asymptoticnotations
recurrence
+3
votes
1
answer
15
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)

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

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

46
views
recurrence
discretemathematics
+1
vote
2
answers
18
#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
(
459
points)

61
views
recurrence
0
votes
0
answers
19
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
(
645
points)

39
views
generatingfunctions
recurrence
+1
vote
1
answer
20
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.8k
points)

497
views
algorithms
timecomplexity
recurrence
programminginc
0
votes
1
answer
21
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.8k
points)

490
views
algorithms
recurrence
timecomplexity
recursion
0
votes
0
answers
22
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)

105
views
relations
recurrence
algorithms
timecomplexity
recurrenceeqation
0
votes
0
answers
23
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
(
251
points)

84
views
timecomplexity
asymptoticnotations
recurrence
algorithms
0
votes
1
answer
24
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)

116
views
recurrence
algorithms
timecomplexity
jest
0
votes
1
answer
25
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.7k
points)

141
views
asymptoticnotations
recurrence
0
votes
1
answer
26
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
(
979
points)

77
views
algorithms
recurrenceeqation
recurrence
+1
vote
1
answer
27
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
(
3.7k
points)

104
views
timecomplexity
algorithms
asymptoticnotations
recurrence
0
votes
0
answers
28
Recurrence relation
Let $a_{n}$ be the number of $n$bit strings that do NOT contain two consecutive $1's.$ Which one of the following is the recurrence relation for $a_{n}?$ $A)a_{n}=a_{n1}+2a_{n2}$ $B)a_{n}=a_{n1}+a_{n2}$ $C)a_{n}=2a_{n1}+a_{n2}$ $D)a_{n}=2a_{n1}+2a_{n2}$
asked
Oct 24, 2018
in
Combinatory
by
Lakshman Patel RJIT
Boss
(
40k
points)

73
views
discretemathematics
recurrence
relations
0
votes
2
answers
29
Recurrence Relation
Let $T(n) = T(n1) + \frac{1}{n} , T(1) = 1 ;$ then $T(n) = ? $ $O(n^{2})$ $O(logn)$ $O(nlogn)$ $O(n^{2}logn)$
asked
Oct 5, 2018
in
Combinatory
by
Lakshman Patel RJIT
Boss
(
40k
points)

135
views
discretemathematics
recurrence
relations
recurrenceeqation
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
IIITH Preparation and interview experience (M.Tech CSE)
My Journey To iiiTH Mtech Cse 2019
IIIT H INTERVIEW EXPERIENCE 2019
IIITH Interview Experience
Thanks GO!!
Follow @csegate
Recent questions tagged recurrence
Recent Blog Comments
Sir till when i cn get my GO 2020 hardcopy. I cnt...
Wonderful experience bro! Something different...
Congrats
Delivery is not beyond July 15 for first 200...
for address change, to whom we have to mail? As I...
49,548
questions
54,169
answers
187,464
comments
71,120
users