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

0 votes

0 answers

1

Divide and conquer
In quick sort, n numbers the (n/10)th element is selected as pivot using n^2 sortimng time complexity what will be the time complexity of quick sort is..... a)O(nlogn) b)O(n^2) c)O(n^3) d)O(n)

In quick sort, n numbers the (n/10)th element is selected as pivot using n^2 sortimng time complexity what will be the time complexity of quick sort is.....a)O(nlogn)b)O(...

Emankashyap

53 views

Emankashyap asked 6 days ago

1 votes

1 answer

2

Recurrence relation
What is the returned value by the given function below. Algo fun(n) { If(x<=2) return 1; Else { Return fun(n1/2) + n; } } Note : Assume that all the syntax and data type constraints are valid and just check algorithm.

What is the returned value by the given function below.Algo fun(n){ If(x<=2) return 1; Else { Return fun(n1/2) + n; }}Note : Assume that all...

jenilS7

153 views

jenilS7 asked Mar 18

3 votes

4 answers

3

GATE CSE 2024 | Set 2 | Question: 5
Let $\text{T(n)}$ be the recurrence relation defined as follows: \[ \begin{array}{l} T(0)=1, \\ T(1)=2, \text { and } \\ T(n)=5 T(n-1)-6 T(n-2) \text { for } n \geq 2 \end{array} \] Which one of the following statements is TRUE? $T(n)=\Theta\left(2^{n}\right)$ $T(n)=\Theta\left(n 2^{n}\right)$ $T(n)=\Theta\left(3^{n}\right)$ $T(n)=\Theta\left(n 3^{n}\right)$

Let $\text{T(n)}$ be the recurrence relation defined as follows:\[\begin{array}{l}T(0)=1, \\T(1)=2, \text { and } \\T(n)=5 T(n-1)-6 T(n-2) \text { for } n ...

Arjun

2.7k views

Arjun asked Feb 16

3 votes

3 answers

4

GATE CSE 2024 | Set 1 | Question: 32
Consider the following recurrence relation: $T(n)=\left\{\begin{array}{c}\sqrt{n} T(\sqrt{n})+n \text { for } n \geq 1, \\ 1 \quad \text { for } n=1\end{array}\right.$ Which one of the following options is CORRECT? $T(n)=\Theta(n \log \log n)$ $T(n)=\Theta(n \log n)$ $T(n)=\Theta\left(n^2 \log n\right)$ $T(n)=\Theta\left(n^2 \log \log n\right)$

Consider the following recurrence relation:$T(n)=\left\{\begin{array}{c}\sqrt{n} T(\sqrt{n})+n \text { for } n \geq 1, \\ 1 \quad \text { for } n=1\end{array}\right.$Whic...

Arjun

2.2k views

Arjun asked Feb 16

6 votes

2 answers

5

GO Classes Test Series 2024 | Mock GATE | Test 14 | Question: 56
The coefficient of $x^6$ in the expansion of $A(x)$ is, where $ A(x)=\frac{x(1+x)}{(1-x)^3} $

The coefficient of $x^6$ in the expansion of $A(x)$ is, where$$A(x)=\frac{x(1+x)}{(1-x)^3}$$

GO Classes

602 views

GO Classes asked Feb 5

1 votes

0 answers

6

Memory Based GATE DA 2024 | Question: 19
Consider the function $f(n)$, which represents the maximum number of comparisons in binary search on a sorted array of size $n$. Which of the following recursive relationships correctly defines $f(n)$? $f(n) = f\left(\lfloor \frac{n}{2} \rfloor\right) ... \rfloor\right)$ $f(n) = f\left(\lfloor \frac{n}{2} \rfloor\right) + 1$ None of the above

Consider the function $f(n)$, which represents the maximum number of comparisons in binary search on a sorted array of size $n$. Which of the following recursive rela...

GO Classes

183 views

GO Classes asked Feb 4

3 votes

3 answers

7

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

940 views

GO Classes asked Jan 21

7 votes

2 answers

8

GO Classes Test Series 2024 | Mock GATE | Test 11 | Question: 44
Acceptable input for a certain pocket calculator is a finite sequence of characters each of which is either a digit or a sign. The first character must be a digit, the last character must be a digit, and any character that is a sign must be followed by a digit. There ... by $N_k=a N _{k-1}+b N _{k-2}$, for $k \geq 3$. What is $a+ b?$

Acceptable input for a certain pocket calculator is a finite sequence of characters each of which is either a digit or a sign. The first character must be a digit, the la...

GO Classes

578 views

GO Classes asked Jan 13

0 votes

1 answer

9

solve this recurrence relation
T(n) = T(n^1/2) + n doing this in substitution method gives the ans as O(n) but using tree recursion gives the ans as O(nlogn) which of these are correct and which has to be considered for worst case

T(n) = T(n^1/2) + ndoing this in substitution method gives the ans as O(n)but using tree recursion gives the ans as O(nlogn)which of these are correct and which has to be...

vivek1211

280 views

vivek1211 asked Oct 2, 2023

0 votes

1 answer

10

GATE: Algorithms (Source: StackOverflow)

rajishu07

271 views

rajishu07 asked Oct 1, 2023

0 votes

1 answer

11

Recurrence relations
Consider the following function: function X(n,r) { if(r==0 or n == r) then return 1; else return (X(n-1,r-1,) + X(n-1,r)); } Find the worst case time complexity of function X ?

Consider the following function:function X(n,r) { if(r==0 or n == r) then return 1; else return (X(n-1,r-1,) + X(n-1,r)); }Find the worst case time complexity of function...

practicalmetal

394 views

practicalmetal asked Sep 15, 2023

0 votes

0 answers

12

How to solve the following recurrence relation? I get confused when decimals are used in the expression.

$T\left ( n \right )= 8T\left ( \frac{n}{2} \right )+\left ( n\cdot logn \right )^{2.99}$Also can $\mathcal{O}(n^{3})$ be an upper bound to above recurrence relation?

rexritz

319 views

rexritz asked Aug 13, 2023

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