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

7 votes

1 answer

31

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

0 votes

1 answer

32

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

3 votes

1 answer

33

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

7 votes

4 answers

34

GATE CSE 2023 | Question: 5
The Lucas sequence $L_{n}$ is defined by the recurrence relation: \[ L_{n}=L_{n-1}+L_{n-2}, \quad \text { for } \quad n \geq 3, \] with $L_{1}=1$ and $L_{2}=3$ ... $L_{n}=\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^{n}$

The Lucas sequence $L_{n}$ is defined by the recurrence relation:\[L_{n}=L_{n-1}+L_{n-2}, \quad \text { for } \quad n \geq 3,\]with $L_{1}=1$ and $L_{2}=3$.Which one of t...

admin

8.0k views

admin asked Feb 15, 2023

0 votes

1 answer

35

GATE CSE 2023 | Memory Based Question: 15
The Lucas sequence $L_n$ is defined by the recurrence relation: $L_n=L_{n-1}+L_{n-2}$, for $n \geq 3$ with $L_1=1$ and $L_2=3$. Which one of the options given is TRUE? $L_n=\left(\frac{1+\sqrt{5}}{2}\right)^n+\left(\frac{1-\sqrt{5}}{3}\right)^n$ ... $L_n=\left(\frac{1+\sqrt{5}}{2}\right)^n+\left(\frac{1-\sqrt{5}}{2}\right)^n$

The Lucas sequence $L_n$ is defined by the recurrence relation:$L_n=L_{n-1}+L_{n-2}$, for $n \geq 3$ with $L_1=1$ and $L_2=3$.Which one of the options given is TRUE?$L_n=...

GO Classes

1.5k views

GO Classes asked Feb 5, 2023

1 votes

0 answers

36

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

22 votes

1 answer

37

Recurrence Relation - Self Doubt
What is the recurrence relation for the ternary strings of length $n$ which can be constructed using 0,1 or 2 only such that the number of 0’s and number of 1's is odd ?

What is the recurrence relation for the ternary strings of length $n$ which can be constructed using 0,1 or 2 only such that the number of 0’s and number of 1's is od...

P C

1.6k views

P C asked Dec 31, 2022

0 votes

1 answer

38

Solve the simultaneous recurrence relations
an = an−1 + bn−1 bn = an−1 − bn−1 with a0 = 1 and b0 = 2.

an = an−1 + bn−1bn = an−1 − bn−1with a0 = 1 and b0 = 2.

chinman12

374 views

chinman12 asked Nov 25, 2022

0 votes

1 answer

39

#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

40

how to solve T(n)=4T(√n)+3^5n with master theorem
how do i apply master theorem to this?

how do i apply master theorem to this?

mdboi

1.0k views

mdboi asked Oct 29, 2022

1 votes

2 answers

41

how to solve T(n)=2T(n/2)−n^3n with master theorem
how do i apply master theorem to this? T(n)=2T(n/2)−n^3n

how do i apply master theorem to this? T(n)=2T(n/2)−n^3n

mdboi

779 views

mdboi asked Oct 28, 2022

1 votes

1 answer

42

𝑇(𝑛)=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

750 views

mdboi asked Oct 28, 2022

0 votes

1 answer

43

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

0 votes

1 answer

44

How to solve this recurrence T(n)=17T(7n)+n^4

darkswow

529 views

darkswow asked Oct 18, 2022

0 votes

0 answers

45

Recurrence relationship
T(n) = 3T(n-1) -4T(n-2) + 2T(n-3) If n = 0 then T(n) = 1 if n= 1 or 2 then T(n) = 0 What is the generalized solution?

T(n) = 3T(n-1) -4T(n-2) + 2T(n-3)If n = 0 then T(n) = 1 if n= 1 or 2 then T(n) = 0What is the generalized solution?

kumar123

589 views

kumar123 asked Sep 25, 2022

1 votes

1 answer

46

Divide and conquer
How To Solve This Using Divide And Conquer Suppose we are given the two n bit integers, assuming for common sense n as power of 2. It is required to multiply them using Divide & conquer method. What is the divide & conquer recurrence, that would arise for the problem. 1. T(n) = 4T(n/2) + O(1) 2. T(n) = 2T(n/2) + O(n) 3. T(n) = 4T(n/2) + O(n^2) 4. T(n) = 4T(n/2) + O(n)

How To Solve This Using Divide And ConquerSuppose we are given the two n bit integers, assuming for common sense n as power of 2. It is required to multiply them using Di...

[ Jiren ]

490 views

[ Jiren ] asked Aug 28, 2022

3 votes

1 answer

47

Best Open Video Playlist for Recurrence relation Topic | Discrete Mathematics
Please list out the best free available video playlist for Recurrence relation Topic from Discrete Mathematics as an answer here (only one playlist per answer). We'll then select the best playlist and add to GO ... ones are more likely to be selected as best. For the full list of selected videos please see here

Please list out the best free available video playlist for Recurrence relation Topic from Discrete Mathematics as an answer here (only one playlist per answer). We'll the...

Arjun

416 views

Arjun asked Aug 7, 2022

4 votes

2 answers

48

GO Classes Scholarship 2023 | Test | Question: 13
Let $\text{T}_{n}$ be the number of ways to arrange cars in a row with $n$ parking spaces if we can use sedans, SUVs, trucks to park such that a truck requires two spaces, whereas a sedan or SUV requires just one space each, and No two ... i.e. initial conditions are already given, hence no need to compute them)

Let $\text{T}_{n}$ be the number of ways to arrange cars in a row with $n$ parking spaces if we can use sedans, SUVs, trucks to park such that a truck requires two spaces...

GO Classes

988 views

GO Classes asked Aug 6, 2022

0 votes

0 answers

49

Discrete Mathematics and Combinatorics
Solve the recurrence relation $a^{2}n-5a^{2}_{n-1}+4a^{2} _{n-2}=0$, if $a_{0}=4, a_{1}=13, n>1$

Solve the recurrence relation $a^{2}n-5a^{2}_{n-1}+4a^{2} _{n-2}=0$, if $a_{0}=4, a_{1}=13, n>1$

kidussss

482 views

kidussss asked Jul 8, 2022

2 votes

1 answer

50

Recurrence Tree Method
T(n) = 5T(n/3) + T(2n/3) + 1. My answer is BigOmega(n) BigO(n). Am I right? This is a question I found on cs.stackexchange.

T(n) = 5T(n/3) + T(2n/3) + 1.My answer is BigOmega(n) BigO(n). Am I right? This is a question I found on cs.stackexchange.

yuyutsu

628 views

yuyutsu asked Jun 22, 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