Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged asymptotic-notation
0
votes
1
answer
1
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 in Best case = O(n). Why isn't the same concept applicable to selection sort? Why it never comes down from O(n$^2$)?
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...
Mrityudoot
133
views
Mrityudoot
asked
Mar 7
Algorithms
algorithms
sorting
time-complexity
asymptotic-notation
+
–
2
votes
4
answers
2
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.1k
views
Arjun
asked
Feb 16
Algorithms
gatecse2024-set2
algorithms
recurrence-relation
asymptotic-notation
+
–
4
votes
1
answer
3
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)$, and it had to be replaced by $R(m)$, which runs in exponential ... $P(n)$ runs in polynomial time in $n$ if, for each call $Q(m),m \underline<\log \;n.$
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)$...
GO Classes
395
views
GO Classes
asked
Feb 5
Algorithms
goclasses2024-mockgate-14
algorithms
asymptotic-notation
time-complexity
2-marks
+
–
3
votes
1
answer
4
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(n)=\theta(g(n))$. $f(n)=\omega(g(n))$. Both A and B are always true.
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...
GO Classes
271
views
GO Classes
asked
Jan 28
Algorithms
goclasses2024-mockgate-13
goclasses
algorithms
asymptotic-notation
1-mark
+
–
1
votes
0
answers
5
TIFR CSE 2024 | Part B | Question: 1
Consider the following three functions defined for all positive integers $n \geq 0$ ... . Only $\text{(ii)}$ and $\text{(iii)}$ are true All of $\text{(i), (ii)}$, and $\text{(iii)}$ are true.
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...
admin
229
views
admin
asked
Jan 13
Algorithms
tifr2024
algorithms
asymptotic-notation
+
–
0
votes
1
answer
6
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, \\ \forall n>1 & f(n) & =3 f(n / 3)+n^{2}, \\ \forall n>1 & g( ... $g(n)=\Theta(n \log \log n)$ $f(n)=\Theta\left(n^{2} \log n\right)$ and $g(n)=\Theta(n \log n)$
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, \\\...
admin
183
views
admin
asked
Jan 13
Algorithms
tifr2024
algorithms
asymptotic-notation
+
–
0
votes
1
answer
7
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}$) }$
$\text{Please explain True or False and Why ?}$$\text{1. f(n) = O(f(n/2))}$$\text{2. f(n) = O($f(n)^{2}$) }$
Jiten008
233
views
Jiten008
asked
Dec 2, 2023
Algorithms
algorithms
time-complexity
asymptotic-notation
functions
+
–
2
votes
2
answers
8
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.
How $O(n)+O(n)+O(n)+O(n)+O(n)+….+O(n)=O(n^2)$ but $\neq O(n)$please explain it.
राजकुमारी विसर्पी
383
views
राजकुमारी विसर्पी
asked
Oct 17, 2023
Algorithms
algorithms
asymptotic-notation
self-doubt
+
–
1
votes
1
answer
9
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?
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?
viral8702
426
views
viral8702
asked
Sep 1, 2023
Algorithms
zeal
algorithms
time-complexity
asymptotic-notation
+
–
0
votes
1
answer
10
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 the answer should be false( fyi).
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...
kickassakash
395
views
kickassakash
asked
Jul 4, 2023
DS
asymptotic-notation
goclasses
data-structures
+
–
0
votes
5
answers
11
#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$
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$
amit166
468
views
amit166
asked
Jun 30, 2023
Algorithms
algorithms
asymptotic-notation
+
–
0
votes
0
answers
12
(x+k)^m=O(x^m) is true or false for x and k being constants?
James_Gosling
231
views
James_Gosling
asked
Apr 24, 2023
Algorithms
algorithms
asymptotic-notation
+
–
2
votes
1
answer
13
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^{\log _{3} n} \log \log n\right)$ None of these
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^...
GO Classes
494
views
GO Classes
asked
Mar 26, 2023
Algorithms
goclasses2023-iiith-mock-1
goclasses
algorithms
asymptotic-notation
1-mark
+
–
7
votes
1
answer
14
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
976
views
GO Classes
asked
Mar 26, 2023
Algorithms
goclasses2023-iiith-mock-1
goclasses
algorithms
recurrence-relation
asymptotic-notation
time-complexity
merge-sort
1-mark
+
–
3
votes
0
answers
15
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 !), \log ^{2} n, e^{n}, (\lg n) !$ $\log ^{2} n, \log (n !), (\lg n) !, e^{n}$ $\log ^{2} n, (\lg n) !, \log (n !), e^{n}$
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 !)...
GO Classes
558
views
GO Classes
asked
Mar 26, 2023
Algorithms
goclasses2023-iiith-mock-1
goclasses
algorithms
asymptotic-notation
time-complexity
1-mark
+
–
2
votes
1
answer
16
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)}$ is $O\left(2^{g(n)}\right)$ $f(n)^{2}$ is $O\left(g(n)^{2}\right)$ $f(n)=O\left((f(n))^{2}\right)$ $g(n)=\Omega(g(n))$
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)...
GO Classes
704
views
GO Classes
asked
Mar 26, 2023
Algorithms
goclasses2023-iiith-mock-1
goclasses
algorithms
asymptotic-notation
time-complexity
multiple-selects
1-mark
+
–
5
votes
1
answer
17
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(n)=2^{2 n}$ ... $f(n)=2^{\sqrt{\log n}}\;, \quad g(n)= (\log n)^{100}$
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...
GO Classes
751
views
GO Classes
asked
Mar 26, 2023
Algorithms
goclasses2023-iiith-mock-1
goclasses
algorithms
logarithmic-function
asymptotic-notation
multiple-selects
1-mark
+
–
1
votes
2
answers
18
Chose the correct big- Θ expression to describe: T(N) = T(N / 2) + Log(N/2); T(1) = 1
I
I
ahmed malik
404
views
ahmed malik
asked
Mar 4, 2023
Algorithms
algorithms
time-complexity
asymptotic-notation
+
–
9
votes
4
answers
19
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 \in o(g)$ $f \in \Theta(g)$
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...
admin
9.4k
views
admin
asked
Feb 15, 2023
Algorithms
gatecse-2023
algorithms
asymptotic-notation
multiple-selects
1-mark
+
–
21
votes
4
answers
20
GATE CSE 2023 | Question: 44
Consider functions $\textsf{Function_1}$ and $\textsf{Function_2}$ ... $f_{1}(n) \in \omega\left(f_{2}(n)\right)$ $f_{1}(n) \in O(n)$
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 ...
admin
11.3k
views
admin
asked
Feb 15, 2023
Algorithms
gatecse-2023
algorithms
asymptotic-notation
multiple-selects
2-marks
+
–
Page:
1
2
3
4
5
6
...
19
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register