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
0
answers
1
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
(
941
points)

79
views
timecomplexity
algorithms
recurrence
0
votes
1
answer
2
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
(
267
points)

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

66
views
recurrence
recurrenceeqation
arrays
linearalgebra
operatingsystem
0
votes
0
answers
4
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)

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

63
views
compilerdesign
leftrecursion
grammar
parsing
recurrence
0
votes
0
answers
6
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
(
377
points)

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

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

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

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

42
views
recurrence
discretemathematics
+1
vote
2
answers
11
#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)

57
views
recurrence
0
votes
0
answers
12
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
(
687
points)

38
views
generatingfunctions
recurrence
+1
vote
1
answer
13
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)

233
views
algorithms
timecomplexity
recurrence
programminginc
0
votes
1
answer
14
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)

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

87
views
relations
recurrence
algorithms
timecomplexity
recurrenceeqation
0
votes
0
answers
16
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
(
297
points)

73
views
timecomplexity
asymptoticnotations
recurrence
algorithms
0
votes
1
answer
17
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.6k
points)

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

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

66
views
algorithms
recurrenceeqation
recurrence
+1
vote
1
answer
20
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.9k
points)

95
views
timecomplexity
algorithms
asymptoticnotations
recurrence
0
votes
0
answers
21
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
(
34.4k
points)

70
views
discretemathematics
recurrence
relations
0
votes
1
answer
22
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
(
34.4k
points)

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

179
views
recurrence
algorithms
timecomplexity
recurrenceeqation
discretemathematics
0
votes
3
answers
24
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
(
305
points)

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

36
views
algorithms
timecomplexity
recurrence
0
votes
1
answer
26
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
(
219
points)

112
views
recurrence
relation
binarysearchtree
0
votes
0
answers
27
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.5k
points)

99
views
timecomplexity
asymptoticnotations
recurrence
0
votes
0
answers
28
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.2k
points)

177
views
algorithms
recurrence
timecomplexity
mastertheorem
0
votes
1
answer
29
MadeEasy Subject Test: Algorithms  Recurrence
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)

151
views
madeeasytestseries
recurrence
mastertheorem
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
IIT BHUBANESWAR MTECH WRITTEN TEST/INTERVIEW
GATE score validity queries.
How to prepare for IISC Interdisciplinary Mathematical Sciences Interview
GO Hardcopy for GATE 2020
How to prepare for BARC interview
Follow @csegate
Recent questions tagged recurrence
Recent Blog Comments
10000 to <2000 is really kind of achievement , my...
THey removed it this year... I did not check it,...
even though i am not going for iiit , can you...
I don't think IIITD requires any codechef...
Will apply for IIITB. IIIT D requires a codechef...
50,114
questions
53,223
answers
184,673
comments
70,469
users