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
1
answer
1
Masters theorem
Solve by using master's theorem
asked
1 day
ago
in
Algorithms
by
bts
(
135
points)

33
views
timecomplexity
mastertheorem
algorithms
asymptoticnotations
recurrence
0
votes
1
answer
2
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
(
47
points)

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

110
views
timecomplexity
algorithms
mastertheorem
asymptoticnotations
recurrence
+1
vote
2
answers
4
SelfDoubt
What will be the time complexity of the following recurrence? $$T(n)=3T\sqrt{n}+log(n)$$
asked
Jun 8
in
Algorithms
by
Phlegmatic
(
187
points)

75
views
algorithms
recurrence
0
votes
2
answers
5
recurrence
asked
May 11
in
Algorithms
by
Sanjay Sharma
Boss
(
48.6k
points)

57
views
algorithms
recurrence
0
votes
2
answers
6
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
(
12.6k
points)

80
views
algorithms
recurrence
0
votes
1
answer
7
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
(
911
points)

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

69
views
algorithms
recurrence
0
votes
0
answers
9
Recurrence
When T(n) = a T(n/b) + f(n) If on solving we get g(n) as upper bound solution for the recurrence. Is f(n) = O( g(n) ) always correct?
asked
Apr 3
in
Algorithms
by
smsubham
Loyal
(
6.3k
points)

102
views
recurrence
timecomplexity
algorithms
asymptoticnotations
0
votes
1
answer
10
Kenneth Rosen Recurrence Relation Example 8
asked
Mar 31
in
Combinatory
by
Abhinavg
(
325
points)

112
views
kennethrosen
recurrence
+1
vote
1
answer
11
#Algorithms How to solve this series?
n/2+n/4+n/8+....+4+2+1 = (2logn−1) ? How this evaluates to (2logn−1)
asked
Mar 31
in
Algorithms
by
iarnav
Loyal
(
7.4k
points)

76
views
recurrence
algorithms
timecomplexity
+1
vote
0
answers
12
#Algorithms Solve this recurrence equation only by using Recursion Tree method
asked
Mar 30
in
Algorithms
by
iarnav
Loyal
(
7.4k
points)

78
views
algorithms
recurrence
timecomplexity
0
votes
0
answers
13
How to solve this which involves log.
I came across a term solving a Recurrence Relation using recursion method and it was  2log(n) = n. How's this being solved? Thanks.
asked
Mar 30
in
Algorithms
by
iarnav
Loyal
(
7.4k
points)

79
views
algorithms
recurrence
timecomplexity
+1
vote
1
answer
14
Please help me solve this Recurrence Relation
asked
Mar 29
in
Algorithms
by
iarnav
Loyal
(
7.4k
points)

68
views
algorithms
timecomplexity
recurrence
0
votes
1
answer
15
How to solve this question ?
What is the smallest value of n such that an algorithm whose running time is runs faster than an algorithm whose running time is on the same machine?
asked
Mar 21
in
Algorithms
by
hem chandra joshi
Active
(
4.4k
points)

60
views
recurrence
algorithms
0
votes
2
answers
16
Test series
Consider the variation of the binary search algorithm so that it splits the list into not only into two sets of almost equal sizes but into two sets of size approximately onethirds and Twothird. What is the recurrence equation for this search in worstcase? $T(n) = T(n/2) + 1$ $T(n) = 2T(n/2) + 1$ $T(n) = T(n/3) + 1$ $T(n) = 2T(n/3) + 1$
asked
Mar 6
in
Algorithms
by
Warrior
Loyal
(
6.4k
points)

76
views
algorithms
recurrence
0
votes
2
answers
17
Algorithm
Give complete solution $T(n) =T(n2)+n^2$, if $n >1$ And $1$, if $n=1$
asked
Mar 6
in
Algorithms
by
Pun M
(
89
points)

79
views
algorithms
recurrence
+2
votes
1
answer
18
Algorithm
Give complete solution for $T(n)=T(n2)+2 log n$ If $n>1$ $= 1$ if $n=1$
asked
Mar 6
in
Algorithms
by
Pun M
(
89
points)

68
views
algorithms
recurrence
0
votes
1
answer
19
Uttrakhand Asst. Professor Exam62
The running time of an algorithm $T(n)$, where $n$ is the input size, is given by following: $T(n) = \begin{cases} 8T(n/2) + qn & \text{ if } n>1 \\ p & \text{ if } n = 1 \end{cases}$ where $p$ and $q$ are constants, the order of algorithm is $n^2$ $n^3$ $n$ $n^n$
asked
Mar 2
in
Others
by
gatecse
Boss
(
18k
points)

34
views
uttarakhandasstprof2018
algorithms
recurrence
mastertheorem
+3
votes
1
answer
20
ME test series
asked
Jan 28
in
Algorithms
by
sumit chakraborty
Active
(
1.2k
points)

97
views
madeeasytestseries
recurrence
recursion
+1
vote
0
answers
21
please solve this
$T(n)=2T(\sqrt{n})+logn$
asked
Jan 27
in
Algorithms
by
Rameez Raza
Active
(
2.3k
points)

41
views
recurrence
+1
vote
0
answers
22
please solve this
$T(n)=2T(\sqrt{n})+n$
asked
Jan 27
in
Algorithms
by
Rameez Raza
Active
(
2.3k
points)

63
views
recurrence
+2
votes
1
answer
23
Test Series
Kindly help in solving the following recurrence relation. Solution is given by using Master's Theorem but can it be applied when the parameter 'b' is not an integer? IF not, then how to solve it? options are O(n), O(n^2), O(nlogn), O(n^2 logn)
asked
Jan 26
in
Algorithms
by
Subham Nagar
Junior
(
587
points)

62
views
madeeasytestseries
algorithms
recurrence
+2
votes
0
answers
24
Recurrence
Answer given as 5050 i am getting 4950
asked
Jan 21
in
Combinatory
by
Inspiron
Active
(
1.5k
points)

36
views
recurrence
+5
votes
1
answer
25
Recurrence Relation
$T(n) = 2T(\sqrt{n}) + n$
asked
Jan 20
in
Algorithms
by
Shubhanshu
Boss
(
15.1k
points)

205
views
algorithms
timecomplexity
recurrenceeqation
recurrence
+1
vote
0
answers
26
Recurrence Problem
The runtime of a divideandconquer algorithm is described by the following recurrence: T(n) = 3T(n/2) + O(1). How many subproblems will we have at the 5th level of recursion if the top level is considered to be the 0th level__________?
asked
Jan 20
in
Algorithms
by
Shubhgupta
Active
(
1.3k
points)

65
views
recurrence
algorithms
+1
vote
1
answer
27
Recuurence
Shouldn't the characteristic equation be (1)... But they have given (2) ... kindly help ... thanks
asked
Jan 18
in
Linear Algebra
by
Pawan Kumar 2
Active
(
4.5k
points)

57
views
recurrence
+4
votes
1
answer
28
recurence relation
Which of the following represents most appropriate asymptotic solution for given reccurance: (A) O(n) (B) O(log n) (C) O(log log n) (D) O(log n)2
asked
Jan 15
in
Algorithms
by
Lakshman Patel RJIT
Loyal
(
7.8k
points)

71
views
recurrence
relations
algorithms
+1
vote
0
answers
29
recurrence equation
what is recurrence relation of harmonic number/series ? and it's time complexity
asked
Jan 14
in
Algorithms
by
iarnav
Loyal
(
7.4k
points)

47
views
algorithms
timecomplexity
recurrence
algorithms
+2
votes
0
answers
30
recurrence relation
asked
Jan 13
in
Combinatory
by
pranab ray
Junior
(
895
points)

73
views
recurrence
discretemathematics
Page:
1
2
3
4
5
6
...
8
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
AAI Junior Exceutive(Information Technology)
The 2018 APL Problem Solving Contest
GO Classroom for GATE 2019
Mtech CSE  IITH (TA) Interview Experience
MS Programme @ IIT
Follow @csegate
Gatecse
Recent questions tagged recurrence
Recent Blog Comments
You are welcome.
Oh ok..got it now! Thank you Sir!!
@Arjun Thank You sir.. it is working now.
@Karan Now it should work for you as well as ...
@Sumaiya The red mark is normal  it is just for ...
37,056
questions
44,636
answers
127,000
comments
43,686
users