Recent questions tagged asymptotic-notations

Assume that $f(n)$ and $g(n)$ are asymptotically positive. Which of the following is correct?$f(n)=O(g(n))$ and $g(n)=O(h(n)) \Rightarrow f(n)=\omega(h(n))$$f(n)=\Omega(g...

Let A be a sorted array of distinct integers of length n. Design an algorithm to find an index i such that A[i] = i if such an index exists. If there are more than one su...

Arrange the following in increasing orders of asymptotic complexity.$f1(n)=2^{n}, f2(n)=n^{\frac{3}{2}}, f3(n)=n\log n,f4(n)=n^{\log n}$$f3, f2, f4, f1$$f3, f2, f1, f4$$f...

BigO notation ofT(n)=T(n-1)+ √n ; n>=1 =0. ; Otherwise

Let $S(n)$ be$$S(n)=S(n / 2)+\log (n) .$$What will be asymptotic bound on $S(n)$?$\Theta(n \log n)$$\Theta(\log n)$$\Theta(\log \log n)$$\Theta\left((\log n)^ 2\right)$

Let $T(n)=T(a n)+T(b n)+n,$ where $a+b<1$.What will be asymptotic bound on $T(n)?$$\Theta(n)$$\Theta\left(n^ 2\right)$$\Theta(n \log n)$$\Theta((a+b) \log n)$

Let $T(n)$ be$$T(n)=16 T(n / 4)+n^{2}(\log n)^{3}$$What will be asymptotic bound on $T(n)?$$\Theta\left(n^ 2(\log n)^ 3\right)$$\Theta\left(n^ 2(\log n)^ 4\right)$$\Theta...

Let $T(n)$ be$$T(n)=64 T(n / 4)+8^{\log _{2} n}$$What will be asymptotic bound on $T(n)?$ $\Theta\left(n^ 3(\log n)^ 3\right)$$\Theta\left(n^ 3\right)$$\Theta\left(n^ 3 \...

Let $T(n)$ be$$T(n)=T(\sqrt{n})+\log \log n$$What will be asymptotic bound on $T(n)?$$\Theta(\log n)$$\Theta((\log \log n)^2)$$\Theta(\log \log \log n)$$\Theta(\log \log ...

Let $T(n)$ be$$T(n)=2 T(\sqrt{n})+\log n$$What will be asymptotic bound on $T(n) ?$$\Theta(\log n)$$\Theta(\log \log n)$$\Theta(\log n \log \log n)$$\Theta(n \log n)$

Let $T(n)$ be$$T(n)=T(n-1)+n^{2} $$$$T(1) = 1$$What will be asymptotic bound on $T(n) ?$$\Theta\left(\mathrm{n}^ 2\right)$$\Theta\left(n^ 3\right)$$\Theta\left(n^ 4\right...

Let $T(n)$ be$$T(n)=n^{2}+T(n / 2)+T(n / 4)$$What will be asymptotic bound on $T(n)?$ $\Theta\left(n^ 2\right)$$\Theta\left(n^ 3\right)$$\Theta\left(n^ 4\right)$$\Theta\l...

Let $$T(n)=\sqrt{n} \cdot T(\sqrt{n})+n$$What will be asymptotic bound on $T(n) ?$$\Theta(\sqrt{n} \log n)$$\Theta(\log \log n)$$\Theta(n \log \log n)$$\Theta(\sqrt{n} \l...

Let $T(n)$ be$$T(n)=T(\sqrt{n})+1$$What will be asymptotic bound on $T(n)$?$\Theta(\log n)$$\Theta(\sqrt{n})$$\Theta(\log \log n)$$\Theta\left((\log n)^ 2\right)$

Select the correct asymptotic complexity of an algorithm with runtime $T(n, n)$ where$T(x, c)=\Theta(x) \quad$ for $c \leq 2$,$T(c, y)=\Theta(y) \quad$ for $c \leq 2$, an...

Consider mutually recursive definitions of $T(a, b)$ and $S(c, d)$ :$$\begin{array}{rlr}T(x, c) & =\Theta(x) & \text { for } c \leq 2 \\T(x, y) & =\Theta(x)+S(x, y / 2), ...

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...

Consider a recurrence relation.$$T(n)=\alpha T(n / 2)+n^{2} .$$Let $a \geq 1$ be an integer.Which of the following is/are true?For $\alpha>4, T(n)=\theta\left(n^{\lg \alp...

Let $T(n)$ be$$T(n)=2 T\left(\frac{n}{2}\right)+\frac{n}{\lg n}$$$T(2) =1$What will be asymptotic bound on $T(n) ?$$\Theta\left(n^ 2(\log n)\right)$$\Theta\left(n(\log n)...