Recent questions tagged recurrence-relation / GATE Overflow for GATE CSE

3 votes

1 answer

61

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

297 views

GO Classes asked Jun 19, 2022

3 votes

1 answer

62

GO Classes Test Series 2023 | Algorithms | Test 2 | Question: 12
Let $T(n)$ be $ T(n)=T(\sqrt{n})+1 $ What will be asymptotic bound on $T(n)$? $\Theta(\log n)$ $\Theta(\sqrt{n})$ $\Theta(\log \log n)$ $\Theta\left((\log n)^ 2\right)$

Let $T(n)$ be$$T(n)=T(\sqrt{n})+1$$What will be asymptotic bound on $T(n)$?$\Theta(\log n)$$\Theta(\sqrt{n})$$\Theta(\log \log n)$$\Theta\left((\log n)^ 2\right)$

GO Classes

222 views

GO Classes asked Jun 19, 2022

3 votes

2 answers

63

GO Classes Test Series 2023 | Algorithms | Test 1 | Question: 13
Consider the following recurrence equation $T(n)=A n^{2}+B n+C$. We determine the constants $A, B, C$ using the following recursive equation. Assume $n$ is a power of $2.$ $ T(n)= \begin{cases}4 T(n / 2)+n+6, & n \geq 2 \\ 2, & n=1\end{cases} $ What will be the value of $A+B+C ?$ $1$ $2$ $3$ $4$

Consider the following recurrence equation $T(n)=A n^{2}+B n+C$.We determine the constants $A, B, C$ using the following recursive equation.Assume $n$ is a power of $2.$$...

GO Classes

291 views

GO Classes asked Jun 13, 2022

1 votes

1 answer

64

Solve equation using master theorem T(n) = 8T(n/2) + 3n^2
I can't figure out how to proceed and which case it's falling under after calculating h(n)

I can't figure out how to proceed and which case it's falling under after calculating h(n)

ItzDc

3.0k views

ItzDc asked Jun 3, 2022

1 votes

2 answers

65

recurrence relation
T(K)=5T(K-1)-4T(K-2) with initial condition T(0)=2 and T(1)=3 determine T(10). using recursion i got answer,but can anyone explain above method.

T(K)=5T(K-1)-4T(K-2) with initial condition T(0)=2 and T(1)=3 determine T(10).using recursion i got answer,but can anyone explain above method.

jugnu1337

472 views

jugnu1337 asked Apr 17, 2022

1 votes

1 answer

66

NIELIT 2022 April Scientist B | Section B | Question: 48
The particular solution of the recurrence relation $a_{r+2} – 4a_{r+1} + 4a_{r} = 2^{r}$ is: $r.2^{r}$ $r(r-1)2^{r-1}$ $r(r-1)2^{r-2}$ $r(r-1)2^{r-3}$

The particular solution of the recurrence relation $a_{r+2} – 4a_{r+1} + 4a_{r} = 2^{r}$ is:$r.2^{r}$$r(r-1)2^{r-1}$$r(r-1)2^{r-2}$$r(r-1)2^{r-3}$

soujanyareddy13

1.1k views

soujanyareddy13 asked Apr 12, 2022

0 votes

1 answer

67

What is the recurrence for T(n)=2T(n/4)+sqrt(n) using the Master Theorem
How do I apply the master theorem in the above recurrence? Please give details about which case and on hiow to solve the asymptotic analysis...

How do I apply the master theorem in the above recurrence? Please give details about which case and on hiow to solve the asymptotic analysis...

lucasbbs

6.9k views

lucasbbs asked Feb 28, 2022

1 votes

1 answer

68

CRT-2022
Kindly help

Kindly help

rsansiya111

267 views

rsansiya111 asked Feb 25, 2022

15 votes

6 answers

69

GATE CSE 2022 | Question: 41
Consider the following recurrence: $\begin{array}{} f(1) & = & 1; \\ f(2n) & = & 2f(n) - 1, & \; \text{for}\; n \geq 1; \\ f(2n+1) & = & 2f(n) + 1, & \; \text{for}\; n \geq 1. \end{array}$ Then, which of the following statements is/are $\text{TRUE}?$ ... $f(2^{n}) = 1$ $f(5 \cdot 2^{n}) = 2^{n+1} + 1$ $f(2^{n} + 1) = 2^{n} + 1$

Consider the following recurrence:$$\begin{array}{} f(1) & = & 1; \\ f(2n) & = & 2f(n) – 1, & \; \text{for}\; n \geq 1; \\ f(2n+1) & = & 2f(n) + 1, & \; \text...

Arjun

7.8k views

Arjun asked Feb 15, 2022

1 votes

1 answer

70

Self doubts
T(n)=T(n/5)+T(7n/10)+an a: constant what will be the time complexity of the above recurrence relation?? Please share the approach for this kind of recurrence relation

T(n)=T(n/5)+T(7n/10)+ana: constantwhat will be the time complexity of the above recurrence relation??Please share the approach for this kind of recurrence relation

lalitver10

610 views

lalitver10 asked Jan 4, 2022

0 votes

1 answer

71

Self doubt
T(n)= T(n/3)+T(n/4)+5n , T(1)=c. Find solution using tree method.

T(n)= T(n/3)+T(n/4)+5n , T(1)=c. Find solution using tree method.

abhinav dongre

376 views

abhinav dongre asked Nov 11, 2021

0 votes

1 answer

72

My doubt
What will be the recurrence relation for max heapify. Please explain with example.

What will be the recurrence relation for max heapify. Please explain with example.

_Madhuri

331 views

_Madhuri asked Nov 2, 2021

0 votes

1 answer

73

Master Theorm
which formula to use in master theorm

which formula to use in master theorm

flash12

332 views

flash12 asked Sep 26, 2021

19 votes

3 answers

74

GATE CSE 2021 Set 2 | Question: 39
For constants $a \geq 1$ and $b>1$, consider the following recurrence defined on the non-negative integers: $T(n) = a \cdot T \left(\dfrac{n}{b} \right) + f(n)$ Which one of the following options is correct about the recurrence $T(n)$? If $f(n)$ is $n \log_2(n)$, ... $f(n)$ is $\Theta(n^{\log_b(a)})$, then $T(n)$ is $\Theta(n^{\log_b(a)})$

For constants $a \geq 1$ and $b>1$, consider the following recurrence defined on the non-negative integers:$$T(n) = a \cdot T \left(\dfrac{n}{b} \right) + f(n)$$ Which on...

Arjun

8.2k views

Arjun asked Feb 18, 2021

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