big-o

Consider the following functions, where $n$ is a positive integer. $$ n^{1 / 3}, \log (n), \log (n!), 2^{\log (n)} $$ Which one of the following options lists the functions in incr...

Given an integer array of size N, we want to check if the array is sorted (in either ascending or descending order). An algorithm solves this problem by making a single pass throug...

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?

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

Consider the following three functions. f 1 = 10 n , f 2 = n logn , f 3 = n √n Which one of the following options arranges the functions in the increasing order of asymptotic growt...

Consider the following functions from positive integers to real numbers : $10, \sqrt{n}, n, \log _2 n, \frac{100}{n}$. The CORRECT arrangement of the above functions in increasing...

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

Which of the given options provides the increasing order of asymptotic Complexity of functions f 1 , f 2 , f 3 and f 4 ? f 1 = 2 n f 2 = n 3/2 f 3 (n) = $$n\,\log _2^n$$ f 4 (n) =...

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 - function: double foo(int n){ int i; double sum; if(n == 0) return 1.0; sum = 0.0; for (i = 0; i < n; i++){ sum += foo(i); } return sum; } The space compl...

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?

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?

Let s be a sorted array of n integers. Let t(n) denote the time taken for the most efficient algorithm to determined if there are two elements with sum less than 1000 in s. which o...

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?

Which of the following is false?

The recurrence relation T(1) = 2 T(n) = 3T(n/4) + n has the solution, T(n) equals 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: