Search results for recurrence+time-complexity / GATE Overflow for GATE CSE

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

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

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

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

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

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

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

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

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

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

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

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

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

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