Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Search results for recurrence+time-complexity
24
votes
7
answers
1
GATE CSE 2021 Set 1 | Question: 30
Consider the following recurrence relation. $T\left ( n \right )=\left\{\begin{array} {lcl} T(n ∕ 2)+T(2n∕5)+7n & \text{if} \; n>0\\1 & \text{if}\; n=0 \end{array}\right.$ Which one of the following options is correct? $T(n)=\Theta (n^{5/2})$ $T(n)=\Theta (n\log n)$ $T(n)=\Theta (n)$ $T(n)=\Theta ((\log n)^{5/2})$
Consider the following recurrence relation.$$T\left ( n \right )=\left\{\begin{array} {lcl} T(n ∕ 2)+T(2n∕5)+7n & \text{if} \; n>0\\1 & \text{if}\; n=0 \end{array}\r...
Arjun
23.8k
views
Arjun
asked
Feb 18, 2021
Algorithms
gatecse-2021-set1
algorithms
recurrence-relation
time-complexity
2-marks
+
–
3
votes
3
answers
2
GO Classes Test Series 2024 | Mock GATE | Test 12 | Question: 54
Of the following, which gives the best upper bound for the value of $f(N)$ where $f$ is a solution to the recurrence $ f(2 N+1)=f(2 N)=f(N)+\log N \text { for } N \geq 1, $ with $f(1)=0?$ $O(\log N)$ $O(N \log N)$ $O\left((\log N)^2\right)$ $O(N)$
Of the following, which gives the best upper bound for the value of $f(N)$ where $f$ is a solution to the recurrence$$f(2 N+1)=f(2 N)=f(N)+\log N \text { for } N \geq 1,$...
GO Classes
887
views
GO Classes
asked
Jan 21
Algorithms
goclasses2024-mockgate-12
goclasses
algorithms
recurrence-relation
time-complexity
2-marks
+
–
52
votes
7
answers
3
GATE CSE 2003 | Question: 35
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(21m-39\right)+4$ $\frac{m}{6}\left(4m^2-3m+5\right)$ $\frac{m}{2}\left(3m^{2.5}-11m+20\right)-5$ $\frac{m}{6}\left(5m^3-34m^2+137m-104\right)+\frac{5}{6}$
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(21...
Kathleen
13.8k
views
Kathleen
asked
Sep 16, 2014
Algorithms
gatecse-2003
algorithms
time-complexity
recurrence-relation
difficult
+
–
31
votes
6
answers
4
GATE CSE 2004 | Question: 83, ISRO2015-40
The time complexity of the following C function is (assume $n > 0$) int recursive (int n) { if(n == 1) return (1); else return (recursive (n-1) + recursive (n-1)); } $O(n)$ $O(n \log n)$ $O(n^2)$ $O(2^n)$
The time complexity of the following C function is (assume $n 0$)int recursive (int n) { if(n == 1) return (1); else return (recursive (n-1) + recursive (n-1)); }$O(n)$$...
Kathleen
19.4k
views
Kathleen
asked
Sep 18, 2014
Algorithms
gatecse-2004
algorithms
recurrence-relation
time-complexity
normal
isro2015
+
–
1
votes
6
answers
5
Can we solve the recurrence T(n) = T(n/2) + 2^n by masters theorem, if possible?
I was wondering whether the recurrence T(n) = T(n/2) + 2n could be solved by using master theorem, and what would be the way. I tried solving the recurrence but can't. There is no mention to it in CLRS book. Please help. Thanks in advance.
I was wondering whether the recurrence T(n) = T(n/2) + 2n could be solved by using master theorem, and what would be the way. I tried solving the recurrence but can't. Th...
mohitrai0_0
19.5k
views
mohitrai0_0
asked
Sep 28, 2018
Algorithms
recurrence-relation
algorithms
master-theorem
time-complexity
asymptotic-notation
+
–
7
votes
1
answer
6
GO Classes 2023 | IIITH Mock Test 1 | Question: 12
A list of $n$ arrays, each of length $n$, is passed to an algorithm like merge-sort. The algorithm recursively divides a set of arrays into two parts until there are only two arrays. If there are two arrays, then, as a base case, the algorithm combines or merges both in cost of ... $T(n)=2 T(n / 2)+n$ $T(n)=2 T(n / 2)+n^ 3$ None of these
A list of $n$ arrays, each of length $n$, is passed to an algorithm like merge-sort. The algorithm recursively divides a set of arrays into two parts until there are only...
GO Classes
1.1k
views
GO Classes
asked
Mar 26, 2023
Algorithms
goclasses2023-iiith-mock-1
goclasses
algorithms
recurrence-relation
asymptotic-notation
time-complexity
merge-sort
1-mark
+
–
3
votes
1
answer
7
TIFR CSE 2023 | Part B | Question: 6
What is the solution to the following recurrence? \[ T(n)=\left\{\begin{array}{ll} 1 & \text { if } n \leq 10, \\ \sqrt{n} \cdot T(\sqrt{n})+n & \text { if } n>10. \end{array}\right. \] $T(n)=\Theta\left(n^{2}\right)$ $T(n)=\Theta(n \log n)$ $T(n)=\Theta(n \sqrt{\log n})$ $T(n)=\Theta(n \log \log n)$ None of the above
What is the solution to the following recurrence?\[T(n)=\left\{\begin{array}{ll}1 & \text { if } n \leq 10, \\\sqrt{n} \cdot T(\sqrt{n})+n & \text { if } n>10.\end{array}...
admin
578
views
admin
asked
Mar 14, 2023
Algorithms
tifr2023
algorithms
recurrence-relation
time-complexity
+
–
0
votes
1
answer
8
self doubt
Solve the following recurrences using recursion tree method and write the asymptotic time complexity T(n)=T(n/2)+n^2
Solve the following recurrences using recursion tree method and write the asymptotic time complexity T(n)=T(n/2)+n^2
Çșȇ ʛấẗẻ
423
views
Çșȇ ʛấẗẻ
asked
Mar 14, 2023
Algorithms
time-complexity
recurrence-relation
+
–
1
votes
0
answers
9
Test series
Can anyone solve this recurrence relation T(n) = 3T(n-1) + O(n^2) Its ans is O(3^n n^2)
Can anyone solve this recurrence relation T(n) = 3T(n-1) + O(n^2)Its ans is O(3^n n^2)
MonuKhan
614
views
MonuKhan
asked
Jan 12, 2023
Algorithms
recurrence-relation
algorithms
time-complexity
asymptotic-notation
+
–
0
votes
1
answer
10
#self_doubt
T(n)={ 0:if n<1 1:if n==1 T(n-1)+T(n-2):n>1 } if the stack size is 48 bytes and one stack entry size =4 B then maximum n=? I thought it should be 13 but the answer is 12 T(1) and T(<1) should not be stored they are already given so can we take n=13 so the last call which will be stored will be T(2)
T(n)={0:if n<11:if n==1T(n-1)+T(n-2):n>1}if the stack size is 48 bytes and one stack entry size =4 B then maximum n=?I thought it should be 13 but the answer is 12T(1) an...
Dknights
391
views
Dknights
asked
Nov 23, 2022
Algorithms
algorithms
recurrence-relation
time-complexity
+
–
1
votes
1
answer
11
𝑇(𝑛)=16𝑇(𝑛/4)+5𝑛^3 using the master theorem
how do i apply master theorem to this? 𝑇(𝑛)=16𝑇(𝑛/4)+5𝑛^3
how do i apply master theorem to this? 𝑇(𝑛)=16𝑇(𝑛/4)+5𝑛^3
mdboi
748
views
mdboi
asked
Oct 28, 2022
Algorithms
algorithms
master-theorem
recurrence-relation
asymptotic-notation
time-complexity
+
–
0
votes
1
answer
12
Madeeasy Algorithm
How to solve this recurrence relation T(n)= T(0.09n) + T(0.91n) + cn where c is constant and T(1)=1 options are-
How to solve this recurrence relationT(n)= T(0.09n) + T(0.91n) + cnwhere c is constant and T(1)=1options are-
Shreya2002
1.1k
views
Shreya2002
asked
Oct 27, 2022
Algorithms
made-easy-test-series
algorithms
time-complexity
recurrence-relation
+
–
3
votes
1
answer
13
GO Classes Test Series 2023 | Algorithms | Test 2 | Question: 8
Let $T(n)$ be $ T(n)=T(n-1)+n^{2} $$ T(1) = 1 $ What will be asymptotic bound on $T(n) ?$ $\Theta\left(\mathrm{n}^ 2\right)$ $\Theta\left(n^ 3\right)$ $\Theta\left(n^ 4\right)$ $\Theta\left(n^ 2 \log n\right)$
Let $T(n)$ be$$T(n)=T(n-1)+n^{2} $$$$T(1) = 1$$What will be asymptotic bound on $T(n) ?$$\Theta\left(\mathrm{n}^ 2\right)$$\Theta\left(n^ 3\right)$$\Theta\left(n^ 4\right...
GO Classes
294
views
GO Classes
asked
Jun 19, 2022
Algorithms
goclasses2024-algo-2-weekly-quiz
goclasses
algorithms
recurrence-relation
asymptotic-notation
time-complexity
2-marks
+
–
To see more, click for the
full list of questions
or
popular tags
.
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register