# Recent questions tagged asymptotic-notations 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$
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)$
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)$
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}}}$
5
$if ...F(n)=O(g(n)) Then ...it is true or false 2^{f(n)}=O(2^{g(n)}) Answer with reason$
6
F(n)=O{ [ f(n)]^2} This statement is true or false With reason..
7
Obtain asymptotically tight bounds on $lg\ (n!)$ without using Stirling’s approximation. Instead, evaluate the summation $\sum_{k=1}^{n} lg\ k$.
8
Prove that $n!=\omega(2^n)$ and $n!=o(n^n)$.
9
How can we modify almost any algorithm to have a good best-case running time?
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?
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.
12
1 vote
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?
14
1 vote
15
$\Large T(n) = 2^nT(\frac{n}{2}) + n^n$
16
Show that $K$ $ln$ $K = \Theta (n)$ implies $k=$\Theta$($n$/$lnn$)$.
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.
18
Show that the golden ratio $\phi$ and its conjugate $\hat{\phi}$ both satisfy the equation $x^2=x+1$.
19
Which is asymptotically larger: $lg(lg^*n)$ and $lg^*(lg n)$ ?
1 vote
20
Is the function $\lceil$ $lg$ $n$ $\rceil$!$polynomially bounded ? Is the function$\lceillglgn\rceil$!$ polynomially bounded ?
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.
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))$.
Prove that $o(g(n)) \cap \omega(g(n))$ is the empty set.
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))$.
Is $2^{n+1} = O(2^n)$? $2^{2n} = O(2^n)$?$0 votes 0 answers 26 Explain why the statement, “The running time of algorithm A is at least$O(n^2),$” is meaningless. 0 votes 1 answer 27 Show that for any real constants$a$and$b$, where$b > 0,(n+a)^b=\Theta(n^b)\$