search
Log In

Recent questions tagged asymptotic-notations

0 votes
1 answer
1
Two alternative package $A$ and $B$ are available for processing a database having $10^{k}$ records. Package $A$ requires $0.0001 n^{2}$ time units and package $B$ requires $10n\log _{10}n$ time units to process $n$ records. What is the smallest value of $k$ for which package $B$ will be preferred over $A$? $12$ $10$ $6$ $5$
asked Apr 2, 2020 in Algorithms Lakshman Patel RJIT 191 views
0 votes
2 answers
2
What is the running time of the following function (specified as a function of the input value)? void Function(int n){ int i=1; int s=1; while(s<=n){ i++; s=s+i; } } $O(n)$ $O(n^2)$ $O(1)$ $O(\sqrt n)$
asked Mar 30, 2020 in Algorithms Lakshman Patel RJIT 445 views
0 votes
2 answers
3
The asymptotic upper bound solution of the recurrence relation given by $T(n)=2T \left ( \frac{n}{2} \right)+\frac{n}{\lg n} $ is: $O(n^{2})$ $O(n \lg n)$ $O(n \lg \lg n)$ $O(\lg \lg n)$
asked Mar 24, 2020 in Algorithms jothee 317 views
5 votes
4 answers
4
Among the following asymptotic expressions, which of these functions grows the slowest (as a function of $n$) asymptotically? $2^{\log n}$ $n^{10}$ $(\sqrt{\log n})^{\log ^{2} n}$ $(\log n)^{\sqrt{\log n}}$ $2^{2^{\sqrt{\log\log n}}}$
asked Feb 11, 2020 in Algorithms Lakshman Patel RJIT 613 views
0 votes
3 answers
5
$if ...F(n)=O(g(n)) Then ...it is true or false 2^{f(n)}=O(2^{g(n)}) Answer with reason$
asked Sep 22, 2019 in Algorithms shubhamkks1005 146 views
0 votes
2 answers
6
F(n)=O{ [ f(n)]^2} This statement is true or false With reason..
asked Sep 22, 2019 in Algorithms shubhamkks1005 144 views
0 votes
1 answer
7
Obtain asymptotically tight bounds on $lg\ (n!)$ without using Stirling’s approximation. Instead, evaluate the summation $\sum_{k=1}^{n} lg\ k$.
asked Jun 28, 2019 in Algorithms akash.dinkar12 85 views
0 votes
1 answer
9
0 votes
1 answer
10
How to check if a given recurrence relation is in a format that is valid to apply Master’s Theorem? Also, how to distinguish between Master’s Theorem and extended Master’s Theorem?
asked Jun 12, 2019 in Algorithms lolster 331 views
3 votes
1 answer
11
Please give an example case for which all the three conditions $f(n)\neq O(g(n))$, $f(n)\neq \Theta (g(n))$ and $f(n)\neq \Omega (g(n))$ holds true.
asked Jun 1, 2019 in Algorithms Satbir 407 views
1 vote
2 answers
13
If $T1(n) = \Theta(f(n))$ & $T2(n) = \Theta(f(n))$ Then, Is $T1(n) + T2(n) = O(f(n))$ If yes, then how?
asked May 26, 2019 in Algorithms shubhojit1412 633 views
0 votes
0 answers
16
0 votes
0 answers
17
Prove by induction that the $i^{th}$ Fibonacci number satisfies the equality $F_i = \frac{\phi^i-\hat{\phi^i}}{\sqrt{5}}$ where $\phi$ is the golden ratio and $\hat{\phi}$ is its conjugate.
asked Apr 4, 2019 in Algorithms akash.dinkar12 40 views
0 votes
0 answers
18
1 vote
0 answers
20
0 votes
0 answers
21
Show that if $f(n)$ and $g(n)$ are monotonically increasing functions, then so are the functions $f(n) +g(n)$ and $f(g(n))$, and if $f(n)$ and $g(n)$ are in addition nonnegative, then $f(n) . g(n)$ is monotonically increasing.
asked Apr 4, 2019 in Algorithms akash.dinkar12 43 views
0 votes
0 answers
22
We can extend our notation to the case of two parameters $n$ and $m$ that can go to infinity independently at different rates.For a given function $g(n,m)$, we denote by $O(g(n,m))$ the set of functions $O(g(n,m))$ $=$ {$f(n,m) :$ there exist positive constants $c,n_0,$ and ... $n \geq n_0$ or $m \geq m_0$ } Give corresponding definitions for $\Omega(g(n,m))$ and $\Theta(g(n,m))$.
asked Apr 4, 2019 in Algorithms akash.dinkar12 65 views
0 votes
0 answers
24
Prove that the running time of an algorithm is $\Theta (g(n))$ if and only if its worst-case running time is $O(g(n))$ and its best-case running time is $\Omega(g(n))$.
asked Apr 4, 2019 in Algorithms akash.dinkar12 43 views
0 votes
0 answers
26
0 votes
1 answer
27
...