The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
Facebook Login
Google Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
All Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous
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
How to solve the following recurrence relation? T(n) = T(n6) + n2 , n>7 T(n) = 1 , n<= 7
asked
1 day
ago
in
Algorithms
by
garvit_vijai
(
123
points)

13
views
timecomplexity
asymptoticnotations
recurrence
algorithms
0
votes
1
answer
2
What is the value of T(n) for the given recurrence relation
asked
3 days
ago
in
Algorithms
by
sripo
Junior
(
751
points)

47
views
recurrence
algorithms
timecomplexity
jest
0
votes
1
answer
3
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
4 days
ago
in
Algorithms
by
Shubham Aggarwal
Active
(
1.2k
points)

105
views
asymptoticnotations
recurrence
0
votes
1
answer
4
Analysis of algorithms of recurrence relation
asked
Oct 31
in
Algorithms
by
Mayankprakash
Junior
(
751
points)

41
views
algorithms
recurrenceeqation
recurrence
+1
vote
1
answer
5
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
in
Algorithms
by
aditi19
Active
(
1.2k
points)

65
views
timecomplexity
algorithms
asymptoticnotations
recurrence
0
votes
0
answers
6
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
in
Combinatory
by
Lakshman Patel RJIT
Boss
(
14.4k
points)

45
views
discretemathematics
recurrence
relations
0
votes
1
answer
7
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
in
Combinatory
by
Lakshman Patel RJIT
Boss
(
14.4k
points)

61
views
discretemathematics
recurrence
relations
recurrenceeqation
+1
vote
3
answers
8
recurrence relation MIT
$T(n)=\sqrt{n} T(\sqrt{n})+100n$ Please solve this.
asked
Oct 4
in
Algorithms
by
sushmita
Boss
(
15k
points)

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

98
views
recurrence
algorithms
mastertheorem
timecomplexity
asymptoticnotations
0
votes
1
answer
10
Verification of the Time Complexities
Can someone please validate the following respective time complexities?
asked
Sep 13
in
Algorithms
by
chauhansunil20th
Junior
(
791
points)

27
views
algorithms
timecomplexity
recurrence
0
votes
1
answer
11
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
in
DS
by
K ANKITH KUMAR
(
191
points)

28
views
recurrence
relation
binarysearchtree
0
votes
0
answers
12
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 ... )$ so $O( 7 ^ {n/53})$ is asymptotically faster But i am not able to get the answer because of question statement .
asked
Aug 22
in
Algorithms
by
Rishav Kumar Singh
Active
(
4.4k
points)

76
views
timecomplexity
asymptoticnotations
recurrence
0
votes
0
answers
13
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
in
Algorithms
by
pradeepchaudhary
Junior
(
749
points)

98
views
algorithms
recurrence
timecomplexity
mastertheorem
0
votes
1
answer
14
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
in
Algorithms
by
manvi_agarwal
(
109
points)

122
views
recurrence
algorithms
master
theorem
timecomplexity
0
votes
2
answers
15
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
in
Algorithms
by
manvi_agarwal
(
109
points)

68
views
timecomplexity
algorithms
mastertheorem
asymptoticnotations
recurrence
0
votes
0
answers
16
RECURRENCE RELATION DOUBT
Which of the following methods enlisted can be termed as best and appropriate for solving recurrence relation? 1)Substitution Method 2)Recurrence Tree 3)Master's Theorem
asked
Aug 7
in
Algorithms
by
Devshree Dubey
Boss
(
13.6k
points)

25
views
algorithms
recurrence
0
votes
1
answer
17
Masters Theorem
How can we apply Masters theorem to these equations : T(n) = 16*T(n/4) + n! and T(n) = 4*T(n/2) + cn Please explain the process.
asked
Aug 6
in
Algorithms
by
Rahul Ranjan 1
(
151
points)

95
views
mastertheorem
timecomplexity
algorithms
asymptoticnotations
recurrence
0
votes
1
answer
18
Recurrence Relation
Solve the following recurrence relation : N(h)=N(h−1)+N(h−2)+1
asked
Jul 27
in
Programming
by
bts
(
149
points)

86
views
recurrence
timecomplexity
recurrenceeqation
algorithms
0
votes
1
answer
19
Linear Recurrence relations
$\text{What is the general form of homogeneous solution for linear nonhomogeneous recurrence relation }$ $a_n = 8 a_{n2}  16a_{n4}$
asked
Jul 22
in
Combinatory
by
!KARAN
Junior
(
665
points)

27
views
recurrence
+1
vote
2
answers
20
Permutation and Combination
How many $10$  digit strings of $0's$ and $1's$ are there that do not contain any consecutive $0's$?
asked
Jul 18
in
Numerical Ability
by
imnitish
Junior
(
657
points)

132
views
permutationsandcombinations
recurrence
0
votes
1
answer
21
Masters theorem
Solve by using master's theorem
asked
Jul 17
in
Algorithms
by
bts
(
149
points)

97
views
timecomplexity
mastertheorem
algorithms
asymptoticnotations
recurrence
0
votes
1
answer
22
UGCNETJuly2018II21
The solution of the recurrence relation $T(m) = T(3m/4)+1$ is $\theta \: (lg \: m)$ $\theta \: (m)$ $\theta \: (mlg \: m)$ $\theta \: (lglg \: m)$
asked
Jul 13
in
Algorithms
by
Pooja Khatri
Active
(
5k
points)

86
views
ugcnetjuly2018ii
algorithms
timecomplexity
recurrence
0
votes
1
answer
23
Time complexity
What is the time complexity of the following recursive function : int DoSomething(int n) { if (n <= 2) return 1; else return DoSomething(floor(sqrt(n)))+ n; } $\theta(n^2)$ $\theta(n \log_2 n)$ $\theta(\log_2 n)$ $\theta(\log_2 \log_2 n)$
asked
Jun 17
in
Algorithms
by
shweta sah
(
49
points)

66
views
algorithms
timecomplexity
recurrence
+2
votes
1
answer
24
Extended Master's Theorem $T(n)=n^{1/2}T(n^{1/2})+n$
asked
Jun 11
in
Algorithms
by
Hardik Maheshwari
(
81
points)

210
views
timecomplexity
algorithms
mastertheorem
asymptoticnotations
recurrence
0
votes
1
answer
25
Recurrence Relation
How to solve using recursion tree method T(n) = T(n/2) + c ; n > 1 T(n) = C ; n = 1
asked
Jun 10
in
Algorithms
by
Lakshman Patel RJIT
Boss
(
14.4k
points)

151
views
algorithms
recurrence
relations
+1
vote
2
answers
26
SelfDoubt
What will be the solution of the following recurrence? $$T(n)=3T\sqrt{n}+\log(n)$$
asked
Jun 8
in
Algorithms
by
Phlegmatic
(
187
points)

118
views
algorithms
recurrence
0
votes
2
answers
27
recurrence
asked
May 11
in
Algorithms
by
Sanjay Sharma
Boss
(
49.6k
points)

59
views
algorithms
recurrence
0
votes
2
answers
28
Algorithm Doubt
How to compute the nth term of fibonacci series 1,1,2,3,5........ ?
asked
Apr 27
in
Algorithms
by
Devshree Dubey
Boss
(
13.6k
points)

85
views
algorithms
recurrence
0
votes
1
answer
29
IIT MS Question
find T(n) = T(n1)*T(n2), given T(1) = a and T(2) = b
asked
Apr 25
in
Algorithms
by
bittu
Junior
(
921
points)

282
views
recurrence
divideandconquer
+1
vote
1
answer
30
Solve the Recurrence
$T(n)=T(\sqrt{n})+n$ $T(2)=1$
asked
Apr 6
in
Algorithms
by
Abhishek Malik
(
213
points)

72
views
algorithms
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
Basic LaTeX guide
IIT Madras Phd
Databases GO Classroom
Happy Birthday Sir Arjun
NIELIT EXAM DATE 2018
Follow @csegate
Gatecse
Recent questions tagged recurrence
Recent Blog Comments
Sir for final year student who have exam in...
I guess you meant while chasing :) Anyway those...
I'll write a post on how to best...
@Gaurav Go through all the previous yr questions,...
42,570
questions
48,556
answers
155,392
comments
63,564
users