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

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

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

49
views
cormen
algorithms
recurrence
timecomplexity
descriptive
+1
vote
1
answer
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
Boss
(
13.1k
points)

129
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
(
213
points)

125
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
(
5.1k
points)

56
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
(
5.1k
points)

53
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
(
5.1k
points)

37
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
(
5.1k
points)

64
views
kennethrosen
discretemathematics
permutationandcombination
#recurrencerelations
recurrence
0
votes
2
answers
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
(
5.1k
points)

59
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
(
815
points)

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

194
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
(
215
points)

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

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

80
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
(
369
points)

266
views
madeeasytestseries
#recurrencerelations
recurrence
+3
votes
1
answer
17
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.6k
points)

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

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

48
views
recurrence
discretemathematics
+1
vote
2
answers
20
#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
(
761
points)

64
views
recurrence
0
votes
0
answers
21
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
(
869
points)

44
views
generatingfunctions
recurrence
+1
vote
1
answer
22
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
(
2.1k
points)

526
views
algorithms
timecomplexity
recurrence
programminginc
+1
vote
2
answers
23
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
(
2.1k
points)

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

136
views
relations
recurrence
algorithms
timecomplexity
recurrenceeqation
0
votes
0
answers
25
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)

93
views
timecomplexity
asymptoticnotations
recurrence
algorithms
0
votes
1
answer
26
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.4k
points)

141
views
recurrence
algorithms
timecomplexity
jest
0
votes
1
answer
27
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)

149
views
asymptoticnotations
recurrence
0
votes
1
answer
28
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)

100
views
algorithms
recurrenceeqation
recurrence
+1
vote
1
answer
29
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
(
5.1k
points)

126
views
timecomplexity
algorithms
asymptoticnotations
recurrence
0
votes
0
answers
30
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
Veteran
(
54.7k
points)

78
views
discretemathematics
recurrence
relations
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
Linear Algebra Important Points
GATE 2020
OFFICIAL GATE MOCK TEST RELEASED
IIITH: Winter Research Admissions 2019 (For Spring 2020)
TIFR and JEST exam
Follow @csegate
Recent questions tagged recurrence
Recent Blog Comments
i also don't have any pdf, actually, I added the...
i don't have , if you have upload it
@mohan123 Do you have all standard book...
bro can be upload all standard book questions in...
it'll take 34 days but for most purpose you can...
50,648
questions
56,441
answers
195,294
comments
100,085
users