worst cases Quiz - ICSE Class 12 Computer Science

Free practice quiz: worst cases (ICSE Class 12 Computer Science). 54 multiple-choice questions with answers and explanations. Play online, no sign-up needed.

Sample questions

1. Consider a recursive function `f(n)` defined as follows: `f(n) = f(n-1) + f(n-2)` for `n > 1`, with `f(0) = 0` and `f(1) = 1`. What is the Big-O complexity of this function in the worst case?

   1. O(n)
   2. O(n^2)
   3. O(2^n)
   4. O(log n)
   Show answer

   Answer: C. O(2^n)

   This recursive relation is the definition of the Fibonacci sequence. Without memoization or dynamic programming, each call branches into two subproblems. The recurrence tree has a depth of n, and at each level, the number of nodes roughly doubles, leading to an exponential time complexity of O(2^n).

2. Consider an algorithm that iterates through a matrix of size N x M, performing a constant time operation for each element. What is the time complexity of this algorithm?

   1. O(N + M)
   2. O(N * M)
   3. O(log(N*M))
   4. O(N^2 * M^2)
   Show answer

   Answer: B. O(N * M)

   The algorithm visits each element in the N x M matrix exactly once. For each element, it performs a constant number of operations. Therefore, the total number of operations is proportional to the total number of elements, which is N * M. The time complexity is O(N * M).

3. Consider an algorithm that performs `n` operations, and for each operation, it calls another function that takes O(log n) time. What is the overall time complexity?

   1. O(n)
   2. O(n log n)
   3. O(n^2)
   4. O(log n)
   Show answer

   Answer: B. O(n log n)

   The algorithm performs `n` independent operations. Each of these operations takes O(log n) time. Therefore, the total time complexity is the product of the number of operations and the time complexity of each operation: n * O(log n) = O(n log n).

4. Which of the following best describes the worst-case time complexity of Bubble Sort?

   1. O(n)
   2. O(n log n)
   3. O(n^2)
   4. O(n^3)
   Show answer

   Answer: C. O(n^2)

   Bubble Sort works by repeatedly stepping through the list, comparing adjacent elements and swapping them if they are in the wrong order. In the worst case (e.g., when the array is sorted in reverse order), it requires approximately n^2/2 comparisons and swaps, leading to a time complexity of O(n^2).

5. What is the worst-case time complexity of insertion sort when the input array is already sorted in ascending order?

   1. O(1)
   2. O(log n)
   3. O(n)
   4. O(n^2)
   Show answer

   Answer: C. O(n)

   Insertion sort's worst-case complexity is O(n^2), which occurs when the array is sorted in reverse order. However, when the array is already sorted in ascending order, for each element `i`, the inner loop (which shifts elements) will execute zero times because the element `i` is already in its correct sorted position relative to the elements before it. Thus, the algorithm performs `n-1` comparisons but no shifts, making its best-case time complexity O(n). The question asks for the worst-case *when sorted ascending*, which is a contradiction in standard definition. The worst-case for insertion sort is reverse sorted (O(n^2)). The best-case for insertion sort is already sorted (O(n)). Assuming the question meant 'best-case when the input array is already sorted in ascending order', the answer is O(n). If it strictly meant 'worst-case' in general, then O(n^2). Given the options and the phrasing, it's likely testing the best-case scenario for insertion sort when the input is sorted.

Browse all average quizzes