Asymptotic Notations Practice Questions

Which of the following case does not exist in complexity theory?

• Best case

• •Worst case

• •Average case

• Null case

•The worst case complexity for insertion sort is _________

•

• O(n)

  •

• O(log n)

• •O(n²)

• •O(n log n)

int fun(int n)

•{

•int count = 0;

•for (int i = 0; i < n; i++)

•for (int j = i; j > 0; j--)

count = count + 1;

•return count;

•}

• Theta (n)

• Theta (n^2)

• •Theta (n*Logn)

• •Theta (nLognLogn)

What does it mean when we say that an algorithm X is asymptotically more efficient than Y?

• X will always be a better choice for small inputs

• •X will always be a better choice for large inputs

• •Y will always be a better choice for small inputs

• •X will always be a better choice for all inputs

•What is the time complexity of following code:

•int a = 0, b = 0;

•for (i = 0; i < N; i++) {

•a = a + rand();

•}

•for (j = 0; j < M; j++) {

•b = b + rand();

•}

• •O(N * M) time,

• •O(N + M) time,

• None of these

•To measure Time complexity of an algorithm Big O notation is used which:

• describes limiting behaviour of the function

• •characterises a function based on growth of function

• •upper bound on growth rate of the function

• •all of the mentioned

•If for an algorithm time complexity is given by O(n) then complexity of it is:

• •constant

• •linear

• •exponential

• •none of the mentioned

•If for an algorithm time complexity is given by O(1) then complexity of it is:

• •constant

• •polynomial

• •exponential

• •none of the mentioned

Consider the following three claims

1. (n + k)m = Θ(nm), where k and m are constants

2. 2n + 1 = O(2n)

3. 22n + 1 = O(2n)

Which of these claims are correct ?

• (A) 1 and 2

• (B) 1 and 3

• (C) 2 and 3

• (D) 1, 2, and 3

What is the time complexity of this code

int a = 0, i = N;

while (i > 0)

{

a += i;

i /= 2;

}

• O(N)

• O(Sqrt(N))

• O(N / 2)

• O(log N)