Awesome q2a theme
Ask us anything
Toggle navigation
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous Year
Exams
Recent questions tagged recurrence
0
votes
1
answer
Cormen Excersice 4, Question 4.41
Solve the Given Recurrence using the Substitution method (in book it was Recursion Tree method) T(n) = 3T(n/2) + n
asked
Apr 29
in
Algorithms
by
ramcharantej_24
(
22
points)

31
views
cormen
algorithms
recurrence
divideandconquer
0
votes
0
answers
GATE200651, ISRO201634 Video Solution
Consider the following recurrence: $ T(n)=2T\left ( \sqrt{n}\right )+1,$ $T(1)=1$ Which one of the following is true? $ T(n)=\Theta (\log\log n)$ $ T(n)=\Theta (\log n)$ $ T(n)=\Theta (\sqrt{n})$ $ T(n)=\Theta (n)$
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

3
views
algorithms
recurrence
isro2016
gate2006
videosolution
0
votes
0
answers
GATE2016127 Video Solution
Consider the recurrence relation $a_1 =8 , a_n =6n^2 +2n+a_{n1}$. Let $a_{99}=K\times 10^4$. The value of $K$ is __________.
asked
Apr 19
in
Combinatory
by
admin
(
3.6k
points)

1
view
gate20161
permutationandcombination
recurrence
normal
numericalanswers
videosolution
0
votes
0
answers
GATE2017230 Video Solution
Consider the recurrence function $T(n) = \begin{cases} 2T(\sqrt{n})+1, & n>2 \\ 2, & 0 < n \leq 2 \end{cases}$ Then $T(n)$ in terms of $\Theta$ notation is $\Theta(\log \log n)$ $\Theta( \log n)$ $\Theta (\sqrt{n})$ $\Theta(n)$
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

1
view
gate20172
algorithms
recurrence
videosolution
0
votes
0
answers
GATE2015211 Video Solution
Consider the following C function. int fun(int n) { int x=1, k; if (n==1) return x; for (k=1; k<n; ++k) x = x + fun(k) * fun (nk); return x; } The return value of $fun(5)$ is ______.
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

3
views
gate20152
algorithms
identifyfunction
recurrence
normal
numericalanswers
videosolution
0
votes
0
answers
GATE200484 Video Solution
The recurrence equation $ T(1) = 1$ $T(n) = 2T(n1) + n, n \geq 2$ evaluates to $2^{n+1}  n  2$ $2^n  n$ $2^{n+1}  2n  2$ $2^n + n $
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

1
view
gate2004
algorithms
recurrence
normal
videosolution
0
votes
0
answers
GATE200483, ISRO201540 Video Solution
The time complexity of the following C function is (assume $n > 0$) int recursive (int n) { if(n == 1) return (1); else return (recursive (n1) + recursive (n1)); } $O(n)$ $O(n \log n)$ $O(n^2)$ $O(2^n)$
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

2
views
gate2004
algorithms
recurrence
timecomplexity
normal
isro2015
videosolution
0
votes
0
answers
GATE2016239 Video Solution
The given diagram shows the flowchart for a recursive function $A(n)$. Assume that all statements, except for the recursive calls, have $O(1)$ time complexity. If the worst case time complexity of this function is $O(n^{\alpha})$, then the least possible value (accurate up to two decimal positions) of $\alpha$ is ________. Flow chart for Recursive Function $A(n)$.
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

2
views
gate20162
algorithms
timecomplexity
recurrence
normal
numericalanswers
videosolution
0
votes
0
answers
GATE19941.7, ISRO201714 Video Solution
The recurrence relation that arises in relation with the complexity of binary search is: $T(n) = 2T\left(\frac{n}{2}\right)+k, \text{ k is a constant }$ $T(n) = T\left(\frac{n}{2}\right)+k, \text{ k is a constant }$ $T(n) = T\left(\frac{n}{2}\right)+\log n$ $T(n) = T\left(\frac{n}{2}\right)+n$
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

1
view
gate1994
algorithms
recurrence
easy
isro2017
videosolution
0
votes
0
answers
GATE2015339 Video Solution
Consider the following recursive C function. void get(int n) { if (n<1) return; get (n1); get (n3); printf("%d", n); } If $get(6)$ function is being called in $main()$ then how many times will the $get()$ function be invoked before returning to the $main()$? $15$ $25$ $35$ $45$
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

1
view
gate20153
algorithms
recurrence
normal
videosolution
0
votes
0
answers
GATE20022.11 Video Solution
The running time of the following algorithm Procedure $A(n)$ If $n \leqslant 2$ return ($1$) else return $(A( \lceil \sqrt{n} \rceil))$; is best described by $O(n)$ $O(\log n)$ $O(\log \log n)$ $O(1)$
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

1
view
gate2002
algorithms
recurrence
normal
videosolution
0
votes
0
answers
GATE2008IT44 Video Solution
When $n = 2^{2k}$ for some $k \geqslant 0$, the recurrence relation $T(n) = √(2) T(n/2) + √n$, $T(1) = 1$ evaluates to : $√(n) (\log n + 1)$ $√(n) \log n$ $√(n) \log √(n)$ $n \log √n$
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

2
views
gate2008it
algorithms
recurrence
normal
videosolution
0
votes
0
answers
GATE200335 Video Solution
Consider the following recurrence relation $T(1)=1$ $T(n+1) = T(n)+\lfloor \sqrt{n+1} \rfloor$ for all $n \geq 1$ The value of $T(m^2)$ for $m \geq 1$ is $\frac{m}{6}\left(21m39\right)+4$ $\frac{m}{6}\left(4m^23m+5\right)$ $\frac{m}{2}\left(3m^{2.5}11m+20\right)5$ $\frac{m}{6}\left(5m^334m^2+137m104\right)+\frac{5}{6}$
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

1
view
gate2003
algorithms
timecomplexity
recurrence
difficult
videosolution
0
votes
0
answers
GATE19992.21 Video Solution
If $T_1 = O(1)$, give the correct matching for the following pairs: $\begin{array}{ll}\hline \text{(M) $T_n = T_{n1} + n$} & \text{(U) $T_n = O(n)$} \\\hline \text{(N) $T_n = T_{n/2} + n$} & \text{(V) $T_n = O(n \log n)$} \\\hline \text{(O) $T_n = T_{n/2} + n ... $\text{MW, NU, OX, PV}$ $\text{MV, NW, OX, PU}$ $\text{MW, NU, OV, PX}$
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

1
view
gate1999
algorithms
recurrence
asymptoticnotations
normal
videosolution
0
votes
0
answers
GATE2014213 Video Solution
Which one of the following correctly determines the solution of the recurrence relation with $T(1) = 1$? $T(n)= 2T\left(\frac {n} {2}\right) + \log n$ $\Theta(n)$ $\Theta(n\log n)$ $\Theta(n^2)$ $\Theta(\log n)$
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

2
views
gate20142
algorithms
recurrence
normal
videosolution
0
votes
0
answers
GATE2015149 Video Solution
Let a$_{n}$ represent the number of bit strings of length n containing two consecutive $1$s. What is the recurrence relation for $a_{n}$? $a_{n  2} + a_{n  1} + 2^{n  2}$ $a_{n  2} + 2a_{n  1} + 2^{n  2}$ $2a_{n  2} + a_{n  1} + 2^{n  2}$ $2a_{n  2} + 2a_{n  1} + 2^{n  2}$
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

2
views
gate20151
algorithms
recurrence
normal
videosolution
0
votes
0
answers
GATE20021.3 Video Solution
The solution to the recurrence equation $T(2^k) = 3T(2^{k1})+1, T(1) =1$ is $2^k$ $\frac{(3^{k+1}1)}{2}$ $3^{\log_2 k}$ $2^{\log_3 k}$
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

1
view
gate2002
algorithms
recurrence
normal
videosolution
0
votes
0
answers
GATE201612 Video Solution
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_n = a_{n1}+ 2a_{n2}$ $a_n = a_{n1}+ a_{n2}$ $a_n = 2a_{n1}+ a_{n2}$ $a_n = 2a_{n1}+ 2a_{n2}$
asked
Apr 19
in
Combinatory
by
admin
(
3.6k
points)

1
view
gate20161
permutationandcombination
recurrence
easy
videosolution
0
votes
0
answers
GATE201216 Video Solution
The recurrence relation capturing the optimal execution time of the $Towers \ of \ Hanoi$ problem with $n$ discs is $T(n) = 2T(n − 2) + 2$ $T (n) = 2T(n − 1) + n$ $T (n) = 2T(n/2) + 1$ $T (n) = 2T(n − 1) + 1$
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

1
view
gate2012
algorithms
easy
recurrence
videosolution
0
votes
0
answers
GATE200537 Video Solution
Suppose $T(n) =2T (\frac{n}{2}) + n$, $T(0) = T(1) =1$ Which one of the following is FALSE? $T(n)=O(n^2)$ $T(n)=\Theta(n \log n)$ $T(n)=\Omega(n^2)$ $T(n)=O(n \log n)$
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

1
view
gate2005
algorithms
asymptoticnotations
recurrence
normal
videosolution
0
votes
0
answers
GATE200935 Video Solution
The running time of an algorithm is represented by the following recurrence relation: $T(n) = \begin{cases} n & n \leq 3 \\ T(\frac{n}{3})+cn & \text{ otherwise } \end{cases}$ Which one of the following represents the time complexity of the algorithm? $\Theta(n)$ $\Theta(n \log n)$ $\Theta(n^2)$ $\Theta(n^2 \log n)$
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

3
views
gate2009
algorithms
recurrence
timecomplexity
normal
videosolution
0
votes
0
answers
GATE201512 Video Solution
Which one of the following is the recurrence equation for the worst case time complexity of the quick sort algorithm for sorting $n$ ( $\geq $ 2) numbers? In the recurrence equations given in the options below, $c$ is a constant. $T(n) = 2 T (n/2) + cn$ $T(n) = T ( n  1) + T(1) + cn$ $T(n) = 2T ( n  1) + cn$ $T(n) = T (n/2) + cn$
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

1
view
gate20151
algorithms
recurrence
sorting
easy
videosolution
0
votes
0
answers
GATE200878 Video Solution
Let $x_n$ denote the number of binary strings of length $n$ that contain no consecutive 0s. Which of the following recurrences does $x_n$ satisfy? $x_n = 2x_{n1}$ $x_n = x_{\lfloor n/2 \rfloor} + 1$ $x_n = x_{\lfloor n/2 \rfloor} + n$ $x_n = x_{n1} + x_{n2}$
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

1
view
gate2008
algorithms
recurrence
normal
videosolution
0
votes
0
answers
GATE2005IT51 Video Solution
Let $T(n)$ be a function defined by the recurrence $T(n) = 2T(n/2) + \sqrt n$ for $n \geq 2$ and $T(1) = 1$ Which of the following statements is TRUE? $T(n) = \Theta(\log n)$ $T(n) = \Theta(\sqrt n)$ $T(n) = \Theta(n)$ $T(n) = \Theta(n \log n)$
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

1
view
gate2005it
algorithms
recurrence
easy
videosolution
0
votes
0
answers
GATE2004IT34 Video Solution
Let $H_1, H_2, H_3,$ ... be harmonic numbers. Then, for $n \in Z^+$, $\sum_{j=1}^{n} H_j$ can be expressed as $nH_{n+1}  (n + 1)$ $(n + 1)H_n  n$ $nH_n  n$ $(n + 1) H_{n+1}  (n + 1)$
asked
Apr 19
in
Combinatory
by
admin
(
3.6k
points)

2
views
gate2004it
recurrence
permutationandcombination
normal
videosolution
0
votes
0
answers
GATE19962.12 Video Solution
The recurrence relation $T(1) = 2$ $T(n) = 3T (\frac{n}{4}) +n$ has the solution $T(n)$ equal to $O(n)$ $O (\log n)$ $O\left(n^\frac{3}{4}\right)$ None of the above
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

2
views
gate1996
algorithms
recurrence
normal
videosolution
0
votes
0
answers
GATE19986a Video Solution
Solve the following recurrence relation $x_n = 2x_{n1}1, n>1$ $x_1=2$
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

0
views
gate1998
algorithms
recurrence
descriptive
videosolution
0
votes
0
answers
GATE2007IT76 Video Solution
Consider the sequence $\langle x_n \rangle , \: n \geq 0$ defined by the recurrence relation $x_{n+1} = c . x^2_n 2$, where $c > 0$. Suppose there exists a nonempty, open interval $(a, b)$ such that for all $x_0$ satisfying $a < x_0 < b$, the ... sequence converges to the value? $\frac{1+\sqrt{1+8c}}{2c}$ $\frac{1\sqrt{1+8c}}{2c}$ $2$ $\frac{2}{2c1}$
asked
Apr 19
in
Combinatory
by
admin
(
3.6k
points)

2
views
gate2007it
permutationandcombination
normal
recurrence
videosolution
0
votes
0
answers
GATE198710a Video Solution
Solve the recurrence equations: $T(n) = T(n  1)+ n$ $T(1) = 1$
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

0
views
gate1987
algorithms
recurrence
videosolution
0
votes
0
answers
GATE200879 Video Solution
Let $x_n$ denote the number of binary strings of length $n$ that contain no consecutive 0s. The value of $x_5$ is $5$ $7$ $8$ $16$
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

1
view
gate2008
algorithms
recurrence
normal
videosolution
0
votes
0
answers
GATE19974.6 Video Solution
Let $T(n)$ be the function defined by $T(1) =1, \: T(n) = 2T (\lfloor \frac{n}{2} \rfloor ) + \sqrt{n}$ for $n \geq 2$. Which of the following statements is true? $T(n) = O \sqrt{n}$ $T(n)=O(n)$ $T(n) = O (\log n)$ None of the above
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

1
view
gate1997
algorithms
recurrence
normal
videosolution
0
votes
0
answers
GATE199017a Video Solution
Express $T(n)$ in terms of the harmonic number $H_{n}= \sum_{t=1}^{n} 1/i, n \geq 1$, where $T(n)$ satisfies the recurrence relation, $T(n)=\frac{n+1}{n} T(n  1)+1$, for $n \geq \sum$ and $T(1) = 1$ What is the asymptotic behaviour of $T(n)$ as a function of $n$ ?
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

3
views
gate1990
descriptive
algorithms
recurrence
videosolution
0
votes
0
answers
GATE2004IT57 Video Solution
Consider a list of recursive algorithms and a list of recurrence relations as shown below. Each recurrence relation corresponds to exactly one algorithm and is used to derive the time complexity of the algorithm. ... $\text{PIII, QII, RIV, SI}$ $\text{PIV, QII, RI, SIII}$
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

1
view
gate2004it
algorithms
recurrence
normal
videosolution
0
votes
0
answers
GATE199207a Video Solution
Consider the function $F(n)$ for which the pseudocode is given below : Function F(n) begin F1 ← 1 if(n=1) then F ← 3 else For i = 1 to n do begin C ← 0 For j = 1 to n – 1 do begin C ← C + 1 end F1 = F1 * C end F = F1 end [$n$ is a positive integer greater than zero] (a) Derive a recurrence relation for $F(n)$
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

2
views
gate1992
algorithms
recurrence
descriptive
videosolution
0
votes
0
answers
GATE198913b Video Solution
Find a solution to the following recurrence equation: $T(n)=\sqrt{n}+T(\frac{n}{2})$ $T(1)=1$
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

2
views
gate1989
descriptive
algorithms
recurrence
videosolution
0
votes
0
answers
GATE199207b Video Solution
Consider the function $F(n)$ for which the pseudocode is given below : Function F(n) begin F1 ← 1 if(n=1) then F ← 3 else For i = 1 to n do begin C ← 0 For j = 1 to n – 1 do begin C ← C + 1 end F1 = F1 * C end F = F1 end [$n$ is a positive integer greater than zero] Solve the recurrence relation for a closed form solution of $F(n)$.
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

1
view
gate1992
algorithms
recurrence
descriptive
videosolution
0
votes
0
answers
GATE199315 Video Solution
Consider the recursive algorithm given below: procedure bubblesort (n); var i,j: index; temp : item; begin for i:=1 to n1 do if A[i] > A[i+1] then begin temp := A[i]; A[i] := A[i+1]; A[i+1] := temp; end; bubblesort (n1) end ... executed when the algorithm is run with value $n$. Set up the recurrence relation by defining $a_n$ in terms of $a_{n1}$. Solve for $a_n$.
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

1
view
gate1993
algorithms
recurrence
normal
videosolution
0
votes
0
answers
GATE198813iv Video Solution
Solve the recurrence equations: $T(n)= T( \frac{n}{2})+1$ $T(1)=1$
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

1
view
gate1988
descriptive
algorithms
recurrence
videosolution
0
votes
0
answers
GATE199715 Video Solution
Consider the following function. Function F(n, m:integer):integer; begin If (n<=0 or (m<=0) then F:=1 else F:F(n1, m) + F(n, m1); end; Use the recurrence relation ... value of $F(n, m)$? How many recursive calls are made to the function $F$, including the original call, when evaluating $F(n, m)$.
asked
Apr 19
in
Algorithms
by
admin
(
3.6k
points)

2
views
gate1997
algorithms
recurrence
normal
videosolution
0
votes
0
answers
GATE19969 Video Solution
The Fibonacci sequence $\{f_1, f_2, f_3 \ldots f_n\}$ is defined by the following recurrence:$f_{n+2} = f_{n+1} + f_n, n \geq 1; f_2 =1:f_1=1$Prove by induction that every third element of the sequence is even.
asked
Apr 19
in
Combinatory
by
admin
(
3.6k
points)

2
views
gate1996
settheory&algebra
recurrence
proof
videosolution
To see more, click for the
full list of questions
or
popular tags
.
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
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Top Users
Jul 2020
Shaik Masthan
39 Points
hiteshpujari
9 Points
Meghana518
6 Points
bittujash
6 Points
Pawan_k
6 Points
srestha
5 Points
RavGopal
4 Points
Anirban Chand
4 Points
Mk Utkarsh
4 Points
abcd9982
3 Points
7,536
questions
1,781
answers
10,866
comments
90,472
users