### Test on time complexity

 Description: 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. Number of Questions: 10 Created by: Swati Sharma Tags: analysis of algorithms aoa time complexity of algorithms
Attempted 0/10 Correct 0 Score 0

What is time complexity of fun()?

int fun(int n)
{
int count = 0;
for (int i = 0; i &lt; n; i++)
for (int j = i; j &gt; 0; j--)
count = count + 1;
return count;
}

1. $\theta(n^2)$

2. $\theta(nlogn)$

3. $\theta(n)$

4. $\theta(logn)^2$

Correct Option: A
Explanation:

To solve this question, the user needs to know the concept of time complexity and how to analyze the time complexity of a given algorithm.

The given function fun() contains two nested loops that iterate over the range of n and j respectively. The outer loop runs n times, and the inner loop runs from i to 1. Therefore, the total number of iterations is the sum of the first n positive integers, which is n*(n+1)/2.

Since the number of iterations is proportional to n^2, the time complexity of the function is $\theta(n^2)$.

The Answer is: A. $\theta(n^2)$

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?

1. A(n) = $\Omega$ W(n)

2. A(n) = $O$ W(n)

3. A(n) = $\Theta$ W(n)

4. A(n) = o W(n)

Correct Option: B

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));
}
}
}

1. $O (n)$

2. $O (n logn)$

3. $O (n^2)$

4. $O (logn)^2$

Correct Option: C

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

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

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

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

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

3. $O(2^n)$ for fun1() and $O(n)$ for fun2()

4. $O(n)$ for both fun1() and fun2()

Correct Option: B
Explanation:

To solve this question, the user needs to know how to determine the time complexity of recursive functions based on the recurrence relation.

Let's analyze the time complexity of each function:

• fun1(n): This function has a recurrence relation of T(n) = T(n-1) + c, where c is a constant representing the time it takes to execute the base case. By repeatedly substituting T(n-1) with T(n-2) and so on, we get T(n) = T(n-k) + kc. When the base case is reached, we have T(n-k) = 1, so T(n) = k + c. Since k is proportional to n, the time complexity of fun1(n) is O(n).

• fun2(n): This function has a recurrence relation of T(n) = 2T(n-1) + c, where c is a constant representing the time it takes to execute the base case. By repeatedly substituting T(n-1) with 2T(n-2), 4T(n-3), and so on, we get T(n) = 2^n * T(0) + c * (2^n - 1). Since T(0) = 1, the time complexity of fun2(n) is O(2^n).

The Answer is: B. O(n) for fun1() and O(2^n) for fun2().

What is not true about insertion sort?

1. Exhibits the worst case performance when the initial array is sorted in reverse order.

2. Worst case and average case performance is Ο(n2)

3. Can be compared to the way a card player arranges his card from a card deck.

4. None of the above!

Correct Option: D
1. $O(n), O(1)$

2. $O(1), O(1)$

3. $O(1), O(n)$

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

Correct Option: B

For a binary search algorithm to work, it is necessary that the array (list) must be

1. sorted

2. unsorted

3. in a heap

4. popped out of stack

Correct Option: A
Explanation:

The correct answer is A. sorted. For a binary search algorithm to work correctly, the array (or list) must be sorted in ascending or descending order. This allows the algorithm to efficiently divide the search space in half at each step, reducing the number of elements to be searched. If the array is unsorted, the binary search algorithm may not produce the correct results.

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

1. $Ο(n^2)$

2. $O(log_2n)$

3. $O(n logn)$

4. $O(log logn)$

Correct Option: B

Recursion uses more memory space than iteration because

1. It uses stack instead of queue.

2. Every recursive call has to be stored.

3. Both 1 & 2 are true.

4. None of the above are true.

Correct Option: B

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

1. 5

2. 4

3. 6

4. 3

Correct Option: D
- Hide questions