Test on time complexity

Time complexity is used for analyzing sorting functions, recursive calculations and things which generally take more computing time. This quiz will test you on this knowledge of calculating time complexity of algorithms.

8 Questions Published

Play Quiz Practise this topic out loud

Questions

Question 1 Multiple Choice (Single Answer)

What is time complexity of fun()?

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^2)$
$\theta(nlogn)$
$\theta(n)$
$\theta(logn)^2$

Question 2 Multiple Choice (Single Answer)

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?

A(n) = $\Omega$ W(n)
A(n) = $O$ W(n)
A(n) = $\Theta$ W(n)
A(n) = o W(n)

Question 3 Multiple Choice (Single Answer)

What is time complexity for the following function?

public void printAllPossibleOrderedPairs ( int[] arrayOfItems)
{  
   for (int firstItem : arrayOfItems)
   { 
       for (int secondItem : arrayOfItems)
       {
           int[] orderedPair = new int[] { firstItem, secondItem};
           system.out.print( Arrays.toString(orderedPair));
       }
   }
}

$O (n)$
$O (n logn)$
$O (n^2)$
$O (logn)^2$

Question 4 Multiple Choice (Single Answer)

Consider the following two functions. What are time complexities of the functions?

int fun1(int n)
{
    if (n <= 1) return n;
    return 2*fun1(n-1);
}

int fun2(int n)
{
    if (n <= 1) return n;
    return fun2(n-1) + fun2(n-1);
}

$O(2^n)$ for both fun1() and fun2()
$O(n)$ for fun1() and $O(2^n)$ for fun2()
$O(2^n)$ for fun1() and $O(n)$ for fun2()
$O(n)$ for both fun1() and fun2()

Question 5 Multiple Choice (Single Answer)

What is not true about insertion sort?

Exhibits the worst case performance when the initial array is sorted in reverse order.
Worst case and average case performance is Ο(n2)
Can be compared to the way a card player arranges his card from a card deck.
None of the above!

Question 6 Multiple Choice (Single Answer)

If queue is implemented using arrays, what would be the worst run time complexity of queue and dequeue operations?

$O(n), O(1)$
$O(1), O(1)$
$O(1), O(n)$
$O(n), \theta(1)$

Question 7 Multiple Choice (Single Answer)

What is the worst case run-time complexity of binary search algorithm?

$Ο(n^2)$
$O(log_2n)$
$O(n logn)$
$O(log logn)$

Question 8 Multiple Choice (Single Answer)

The number of passes needed to sort the numbers 8, 22, 7, 9, 31 in ascending order, using insertion sort is

← Back to Quizzes