The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
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
1
answer
1
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
(
205
points)

72
views
timecomplexity
algorithms
recurrence
recurrenceeqation
0
votes
0
answers
2
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
(
321
points)

52
views
recurrence
recurrenceeqation
arrays
linearalgebra
operatingsystem
0
votes
0
answers
3
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
Active
(
1.1k
points)

99
views
recurrenceeqation
timecomplexity
recurrence
algorithms
+1
vote
0
answers
4
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)

46
views
compilerdesign
leftrecursion
grammar
parsing
recurrence
0
votes
0
answers
5
Q.31 Made easy full test 2  basic level
What’s the trick to do it under 2 min here?
asked
Dec 31, 2018
in
Combinatory
by
shaz
(
347
points)

225
views
madeeasytestseries
#recurrencerelations
recurrence
0
votes
1
answer
6
time complexity
asked
Dec 30, 2018
in
Algorithms
by
Rahul_Rathod_
Junior
(
565
points)

28
views
timecomplexity
algorithms
asymptoticnotations
recurrence
+3
votes
1
answer
7
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.9k
points)

237
views
go2019flt1
asymptoticnotations
recurrence
+1
vote
0
answers
8
https://gateoverflow.in/33989/howtosolvebelowrecurrencerelation
https://gateoverflow.in/33989/howtosolvebelowrecurrencerelation
asked
Dec 23, 2018
in
Combinatory
by
mitesh kumar
(
323
points)

37
views
recurrence
discretemathematics
0
votes
2
answers
9
RosenRecurrence Relation
Find a recurrence relation for the number of bit strings of length n that contains a pair of consecutive 0s
asked
Dec 14, 2018
in
Combinatory
by
aditi19
Active
(
2.3k
points)

49
views
recurrence
kennethrosen
+1
vote
2
answers
10
#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
(
693
points)

54
views
recurrence
0
votes
0
answers
11
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
(
651
points)

36
views
generatingfunctions
recurrence
+1
vote
1
answer
12
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.7k
points)

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

209
views
algorithms
recurrence
timecomplexity
recursion
0
votes
0
answers
14
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
Loyal
(
5.2k
points)

77
views
relations
recurrence
algorithms
timecomplexity
recurrenceeqation
0
votes
0
answers
15
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
(
207
points)

68
views
timecomplexity
asymptoticnotations
recurrence
algorithms
0
votes
1
answer
16
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
(
1.5k
points)

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

131
views
asymptoticnotations
recurrence
0
votes
1
answer
18
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
(
1.1k
points)

60
views
algorithms
recurrenceeqation
recurrence
+1
vote
1
answer
19
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
(
2.3k
points)

92
views
timecomplexity
algorithms
asymptoticnotations
recurrence
0
votes
0
answers
20
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
(
29k
points)

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

92
views
discretemathematics
recurrence
relations
recurrenceeqation
+2
votes
3
answers
22
recurrence relation MIT
$T(n)=\sqrt{n} T(\sqrt{n})+100n$ Please solve this.
asked
Oct 4, 2018
in
Algorithms
by
sushmita
Boss
(
16.8k
points)

165
views
recurrence
algorithms
timecomplexity
recurrenceeqation
discretemathematics
0
votes
3
answers
23
Can we solve the recurrence T(n) = T(n/2) + 2^n by masters theorem, if possible?
asked
Sep 28, 2018
in
Algorithms
by
mohitrai0_0
(
299
points)

166
views
recurrence
algorithms
mastertheorem
timecomplexity
asymptoticnotations
0
votes
1
answer
24
Verification of the Time Complexities
Can someone please validate the following respective time complexities?
asked
Sep 13, 2018
in
Algorithms
by
chauhansunil20th
Active
(
4.8k
points)

33
views
algorithms
timecomplexity
recurrence
0
votes
1
answer
25
Recurrence Relation of BST
Let T (n) be the number of comparisons needed in a binary search of a list of n elements. What is the recurrence relation? Explain. 1) T(n) = T(n/2) + 2 2) T(n) = T(n/2) + 1
asked
Aug 29, 2018
in
DS
by
K ANKITH KUMAR
(
209
points)

62
views
recurrence
relation
binarysearchtree
0
votes
0
answers
26
time complexity
I got this question from here https://gateoverflow.in/169286/timecomplexity Is this Question Correct i have doubt . If correct please explain Which of the following statements is/are TRUE? $i)$ The time complexity of recurrence relation $A(n) = 3A(n/2)+n^{2} $is ... $O( 7 ^ {n/53})$ is asymptotically faster But i am not able to get the answer because of question statement .
asked
Aug 22, 2018
in
Algorithms
by
Rishav Kumar Singh
Loyal
(
5.4k
points)

91
views
timecomplexity
asymptoticnotations
recurrence
0
votes
0
answers
27
Master's Theorem Recurrence Relation
T (n) = T (n/2) + 2n Using Master's Method What is the Complexity Of This Recurrence Relation? Or Using AnyOther Method?
asked
Aug 20, 2018
in
Algorithms
by
pradeepchaudhary
Active
(
1.1k
points)

134
views
algorithms
recurrence
timecomplexity
mastertheorem
0
votes
1
answer
28
made easy, recurrence relations
which of the following cannot be solved using masters theorem? a) T(n) = 2T(n/2) + n/logn b) T(n) = 2T(n/2) + logn c)T(n)=T(n/2)+logn d) non of these
asked
Aug 11, 2018
in
Algorithms
by
manvi_agarwal
(
139
points)

130
views
recurrence
algorithms
master
theorem
timecomplexity
0
votes
2
answers
29
masters theorem
Solution using back substitution method T(n) = 2T(n/2) + nlogn ? detailed solution please. ans is nlognlogn or n(logn)^2
asked
Aug 10, 2018
in
Algorithms
by
manvi_agarwal
(
139
points)

82
views
timecomplexity
algorithms
mastertheorem
asymptoticnotations
recurrence
Page:
1
2
3
4
5
6
...
9
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
Official keys are out now.
JEST 2019 MEMORY BASED QUESTION PAPER
Relax... But....
Barc : Arjun Sir
JEST Sample Question
Follow @csegate
Recent questions tagged recurrence
Recent Blog Comments
How to challenge the key???
There was this graph coloring chromatic number...
Is it 100% same as GO answers?
Ans is 3 , how to challenge key?
@Prateek Raghuvanshi why do you think bonus marks...
47,903
questions
52,285
answers
182,209
comments
67,715
users