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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

24
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

16
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

55
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, 2019
in
Combinatory
by
`JEET
Boss
(
18.9k
points)

146
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, 2019
in
Algorithms
by
kshitij
(
293
points)

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

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

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

56
views
kennethrosen
discretemathematics
#recurrencerelations
recurrence
+2
votes
1
answer
9
ISI2018PCBCS2
You can climb up a staircase of $n$ stairs by taking steps of one or two stairs at a time. Formulate a recurrence relation for counting $a_n$, the number of distinct ways in which you can climb up the staircase. Mention the boundary conditions for your recurrence relation. Find a closed form expression for $a_n$ by solving your recurrence.
asked
May 12, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

56
views
isi2018pcbcs
algorithms
recurrence
descriptive
0
votes
1
answer
10
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, 2019
in
Combinatory
by
aditi19
Active
(
5.2k
points)

73
views
kennethrosen
discretemathematics
permutationandcombination
#recurrencerelations
recurrence
0
votes
2
answers
11
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, 2019
in
Combinatory
by
aditi19
Active
(
5.2k
points)

69
views
kennethrosen
discretemathematics
permutationandcombination
#recurrencerelations
recurrence
0
votes
0
answers
12
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, 2019
in
Algorithms
by
syncronizing
Junior
(
835
points)

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

212
views
timecomplexity
algorithms
recurrence
recurrenceeqation
0
votes
0
answers
14
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)

102
views
recurrence
recurrenceeqation
arrays
linearalgebra
operatingsystem
0
votes
1
answer
15
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, 2019
in
Algorithms
by
Mayankprakash
Active
(
1k
points)

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

95
views
compilerdesign
leftrecursion
grammar
parsing
recurrence
0
votes
0
answers
17
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)

274
views
madeeasytestseries
#recurrencerelations
recurrence
+4
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
Algorithms
by
Ruturaj Mohanty
Active
(
2.7k
points)

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

122
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
Junior
(
569
points)

52
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
(
775
points)

66
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
(
933
points)

48
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
(
2.1k
points)

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

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

149
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
(
263
points)

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

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

151
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
Active
(
1k
points)

105
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
(
5.2k
points)

134
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
ISRO CSE 2020 PAPER ANALYSE
BARC OCES/DGFS 2020
ISI CMI PDF by GATE Overflow
Management Trainee Recruitment COAL INDIA 2020
ECIL Interview Experience
Follow @csegate
Recent questions tagged recurrence
Recent Blog Comments
they were in hurry while setting the papers they...
@Swaraj Right.. In Little Endian  Big endian...
Q42 C option is correct for C set as it is an...
@ smsubham The SQL query question No...
Are SQL query and that case 1, case 2 answer in...
50,737
questions
57,271
answers
198,140
comments
104,781
users