asymptotic-notation

Let T(n) be the recurrence relation defined as follows: T(0) = 1, T(1) = 2, and T(n) = 5T(n - 1) – 6T(n-2) for n ≥ 2 Which one of the following statements is TRUE?

Consider the following recurrence relation: $T(n) = \begin{cases} \sqrt{n}T(\sqrt{n}) + n & \text{for } n \geq 1, \\ 1 & \text{for } n = 1. \end{cases}$ Which one of the following...

Consider the following recurrence relation: $$T(n) = \begin{cases} \sqrt{n} T(\sqrt{n}) + n & \text{for } n \ge 1, \\ 1 & \text{for } n = 1. \end{cases}$$ Which one of the followin...

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 TRUE?

Consider functions Function_1 and Function_2 expressed in pseudocode as follows: Function 1 while n > 1 do for i = 1 to n do x = x + 1; end for n = n/2; end while Function 2 for...

Which one of the following statements is TRUE for all positive functions f(n) ?

For constants a ≥ 1 and b > 1, consider the following recurrence defined on the non-negative integers : $$T\left( n \right) = a.T\left( {\frac{n}{b}} \right) + f\left( n \right)$$...

Consider the following recurrence relation. $$T(n) = \left\{ {\begin{array}{*{20}{c}} {T(n/2) + T(2n/5) + 7n \ \ \ if\ n > 0}\\ {1\ \ \ \ \ \ \ if\ n = 0} \end{array}} \right.$$ Wh...

For parameters a and b, both of which are $$\omega \left( 1 \right)$$, T(n) = $$T\left( {{n^{1/a}}} \right) + 1$$, and T(b) = 1. Then T(n) is

What is the worst case time complexity of inserting n 2 elements into an AVL-tree with n elements initially?

Let $$f\left( n \right) = n$$ and $$g\left( n \right) = {n^{\left( {1 + \sin \,\,n} \right)}},$$ where $$n$$ is a positive integer. Which of the following statements is/are correct...

Consider the equality $$\sum\limits_{i = 0}^n {{i^3}} = X$$ and the following choices for $$X$$ $$\eqalign{ & \,\,\,\,\,\,\,{\rm I}.\,\,\,\,\,\,\Theta \left( {{n^4}} \right) \cr &...

Which one of the following correctly determines the solution of the recurrence relation with T(1) = 1? T(1) = 2T (n/2) + log n

Consider the following function: int unknown(int n) { int i, j, k = 0; for (i = n/2; i <= n; i++) for (j = 2; j <= n; j = j * 2) k = k + n/2; return k; } The return value of the fu...

The worst case running time to search for an element in a balanced binary search tree with n2 n elements is

Let W(n) and A(n) denote respectively, the worst case and average case running time of an algorithm executed on an input of size n. Which of the following is ALWAYS TRUE?

The running time of an algorithm is represented by the following recurrence relation: $$T(n) = \begin{cases} n & n \leq 3 \\ T(\frac{n}{3})+cn & \text{ otherwise } \end{cases}$$ Wh...

Consider the following functions: F(n) = 2 n G(n) = n! H(n) = n logn Which of the following statements about the asymptotic behaviour of f(n), g(n), and h(n) is true?

Consider the following C-program fragment in which i, j and n are integer variables. for (i = n, j = 0; i > 0; i /= 2, j += i); let val (j) denote the value stored in the variable...

Suppose T(n) = 2T (n/2) + n, T(0) = T(1) = 1 Which one of the following is FALSE?

Consider the following three claims I. (n + k) m = $$\Theta \,({n^m})$$ where k and m are constants II. 2 n+1 = O(2 n ) III. 2 2n = O(2 2n ) Which of those claims are correct?

The running time of the following algorithm Procedure A(n) If n<=2 return (1) else return (A([$$\sqrt n $$])); is best described by

Let f(n) = n 2 log n and g(n) = n(log n) 10 be two positive functions of n. Which of the following statements is correct?

Consider the following functions $$f(n) = 3{n^{\sqrt n }}$$ $$g(n) = {2^{\sqrt n {{\log }_2}n}}$$ $$h(n) = n!$$ Which of the following is true?

Let T(n) be the function defined by $$T(1) =1, \: T(n) = 2T (\lfloor \frac{n}{2} \rfloor ) + \sqrt{n}$$ Which of the following statements is true?

Which of the following is false?

The recurrence relation $$\,\,\,\,\,$$ $$T\left( 1 \right) = 2$$ $$T\left( n \right) = 3T\left( {{n \over 4}} \right) + n$$ has the solution $$T(n)$$ equal to

Conside the following two functions: $${g_1}(n) = \left\{ {\matrix{ {{n^3}\,for\,0 \le n < 10,000} \cr {{n^2}\,for\,n \ge 10,000} \cr } } \right.$$ $${g_2}(n) = \left\{ {\matrix{ {...

$$\sum\limits_{1 \le k \le n} {O(n)} $$ where O(n) stands for order n is: