Register

Recent questions tagged asymptotic-notation

279
views
1 answers
0 votes
Sorting Algorithm
For flag based approach in Bubble sort we can check first by a flag if the list is sorted or not in O(n), and if it is sorted, then no need to sort and the operation ends...
User Avatar
3.0k
views
4 answers
4 votes
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 ...
User Avatar
485
views
1 answers
5 votes
GO Classes Test Series 2024 | Mock GATE | Test 14 | Question: 46
We have a procedure $P(n)$ that makes multiple calls to a procedure $Q(m)$, and runs in polynomial time in $n$. Unfortunately, a significant flaw was discovered in $Q(m)$...
User Avatar
335
views
1 answers
4 votes
GO Classes Test Series 2024 | Mock GATE | Test 13 | Question: 14
Given that $f(n)=O(g(n))$ (where $\mathrm{O}$ is Big-O) and $f(n)=\Omega(g(n))$, which of the following statement is always true?$f(n)=o(g(n))$ (here $o$ is small-$o).$$f...
User Avatar
301
views
0 answers
2 votes
TIFR CSE 2024 | Part B | Question: 1
Consider the following three functions defined for all positive integers $n \geq 0$.\[\begin{array}{l}f(n)=|\sin (n)+n|, \\g(n)=n, \\h(n)=|\sin (n)| .\end{array}\]Which o...
User Avatar
250
views
1 answers
1 votes
TIFR CSE 2024 | Part B | Question: 4
Consider functions $f$ and $g$ from the set of positive real numbers to itself, recursively defined as follows.\[\begin{array}{rrl}\forall n \leq 1 & f(n), g(n) & =1, \\\...
User Avatar
289
views
1 answers
0 votes
TS
$\text{Please explain True or False and Why ?}$$\text{1. f(n) = O(f(n/2))}$$\text{2. f(n) = O($f(n)^{2}$) }$
User Avatar
433
views
2 answers
2 votes
Self doubt
How $O(n)+O(n)+O(n)+O(n)+O(n)+….+O(n)=O(n^2)$ but $\neq O(n)$please explain it.
User Avatar
546
views
2 answers
1 votes
test series
int i,j,k,s=0; for(i=1; i<=n; i++) { for(j=1 ; j<=i; j=j*2) { for(k=n; k>1;k=k/2) { s++; } } }What will be the time complexity of the above code?
User Avatar
454
views
1 answers
0 votes
Go Class data structure asymptotic notation practice video question 21
I have specific doubt on this question and I’ve tried to explain that in the picture ,If anyone can explain it then it’ll be of great help. according to sachin sir th...
User Avatar
555
views
5 answers
0 votes
#cpcb
Select the function(s) which is/are $O(n log n)$:$2n\log n+3n$$10n\log n^2$$1+\sqrt n$$2n^2-3n$
User Avatar
293
views
1 answers
3 votes
GO Classes 2024 | IIITH Mock Test 5 | Question: 15
Let $n$ be a positive integer.Consider the two statements below:$\text{S1:}$ If $f(n)>g(n)$ for all $n$ then $g(n)$ is ALWAYS o( $f(n))$. where $o$ is small-oh.$\text{S2:...
User Avatar
756
views
1 answers
2 votes
GO Classes 2023 | IIITH Mock Test 1 | Question: 9
Let $T(n)=4 T(n / 3)+n^{\log _{3} 4}.$ What will be asymptotic bound on $T(n)?$$T(n)=\Theta\left(n^{\log _{3} 4} \log n\right)$$T(n)=\Theta(n \log n)$$T(n)=\Theta\left(4^...
User Avatar
1.5k
views
1 answers
7 votes
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...
User Avatar
875
views
0 answers
3 votes
GO Classes 2023 | IIITH Mock Test 1 | Question: 13
Arrange the following functions in their increasing order of growth. In options $\log ^{2} n$ means $(\log n)^{2}$$\log (n !), \log ^{2} n, (\lg n) !, e^{n}$$\log (n !)...
User Avatar
1.0k
views
1 answers
2 votes
GO Classes 2023 | IIITH Mock Test 1 | Question: 45
Assume you have two positive functions $f$ and $g$ such that $f(n)$ is in $O(g(n))$. For each of the following statements, decide which one(s) is/are always TRUE.$2^{f(n)...
User Avatar
1.2k
views
1 answers
7 votes
GO Classes 2023 | IIITH Mock Test 1 | Question: 50
For which of the following functions $f(n)$ and $g(n),$ it holds $:f(n)=O(g(n)).$ Every $\log$ below is base $2.$$f(n)=2^{k \log n}\;, \quad g(n)=n^k$$f(n)=2^n\;, \quad g...
User Avatar
481
views
2 answers
1 votes
Chose the correct big- Θ expression to describe: T(N) = T(N / 2) + Log(N/2); T(1) = 1
I
User Avatar
10.0k
views
4 answers
10 votes
GATE CSE 2023 | Question: 19
Let $f$ and $g$ be functions of natural numbers given by $f(n)=n$ and $g(n)=n^{2}.$ Which of the following statements is/are $\text{TRUE}?$$f \in O(g)$$f \in \Omega(g)$$f...
User Avatar
12.0k
views
4 answers
21 votes
GATE CSE 2023 | Question: 44
Consider functions $\textsf{Function_1}$ and $\textsf{Function_2}$ expressed in pseudocode as follows:Function_1 | Function_2 while n 1 do | for i = 1 to 100 * n do for ...
User Avatar
Page: