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.

This ICSE Class 12 Computer Science practice quiz has 54 multiple-choice questions on worst cases, and 53 of them come with an explanation. Try the 5 sample questions below (tap an option to check yourself), then play the full quiz 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.

More questions in this quiz

Answers and explanations are in the full quiz.

1. A sorting algorithm has a worst-case time complexity of O(n^2) and a best-case time complexity of O(n log n). Which of the following algorithms best fits this description?
2. Which of the following statements about Big-O notation is FALSE?
3. Consider an algorithm that iterates through a list of `n` elements, and for each element, it performs a constant number of operations. Then, it sorts the list using an algorithm with a time complexity of O(n log n). What is the overall time complexity of this algorithm?
4. An algorithm searches for a specific element in an unsorted array of size `n`. In the worst case, it has to check every element. What is the Big-O complexity of this search operation?
5. Which of the following data structures provides O(1) average time complexity for insertion, deletion, and search operations?
6. Consider an algorithm that performs a binary search on a sorted array of size `n`. What is the Big-O complexity of this algorithm in the worst case?
7. What is the best-case time complexity of an algorithm that iterates through an array of `n` elements and stops as soon as it finds a specific target element?
8. An algorithm has a worst-case time complexity of O(n) and an average-case time complexity of O(n log n). Which of the following sorting algorithms might this be?
9. Which of the following Big-O notations represents a growth rate slower than O(n)?
10. A linear search algorithm on an array of size `n` has a best-case time complexity of O(1). What does this imply about the algorithm?
11. Which of the following Big-O complexities represents an exponential growth rate?
12. Consider an algorithm that processes a sorted list of `n` elements by inserting each element into a Binary Search Tree (BST). What is the average-case time complexity of this entire process if we consider the average case for BST insertions?
13. Which of the following scenarios would result in the worst-case time complexity for Quick Sort?
14. Consider an algorithm that involves nested loops. The outer loop runs `n` times, and the inner loop runs `n` times for each iteration of the outer loop. What is the Big-O complexity of this algorithm?
15. What is the best-case time complexity for searching an element in a Binary Search Tree (BST) containing `n` nodes, assuming the tree is balanced?
16. An algorithm's time complexity is described as O(n^3). If the input size is increased from 100 to 200, by approximately what factor would the execution time increase?
17. Which of the following operations on a standard dynamic array (like Python's list or Java's ArrayList) has an amortized time complexity of O(1)?
18. Consider a recursive function `T(n) = T(n/2) + c`, where `c` is a constant. What is the Big-O complexity of this function?
19. What is the average-case time complexity of searching for an element in a hash table that uses separate chaining for collision resolution, assuming a uniform distribution of keys and a load factor α (alpha)?
20. Which of the following Big-O complexities describes an algorithm that takes roughly the same amount of time regardless of the input size?
21. Consider a scenario where an algorithm performs a constant number of operations, followed by sorting `n` elements using an algorithm with a worst-case time complexity of O(n^2). What is the overall worst-case time complexity?
22. What is the worst-case time complexity for finding the maximum element in an unsorted array of `n` elements?
23. Consider the following function: `for i from 1 to n: for j from i to n: print 'hello'`. What is the Big-O complexity of this code snippet?
24. Which of the following statements about Omega (Ω) notation is FALSE?
25. What is the best-case time complexity for inserting an element into a balanced Binary Search Tree (BST) with `n` nodes?
26. Consider an algorithm that iterates through all possible pairs of elements in an array of size `n`. What is the Big-O complexity of this algorithm?
27. What is the average-case time complexity of searching for an element in a Binary Search Tree (BST) with `n` nodes, assuming the tree is reasonably balanced?
28. If an algorithm's time complexity is O(n), and the input size `n` is multiplied by 3, by approximately what factor will the execution time increase?
29. Consider a recursive function `f(n) = 2 * f(n/2) + n`. What is the Big-O complexity of this function?
30. What is the average-case time complexity for inserting an element into a hash table that uses linear probing for collision resolution, assuming a uniform distribution of keys and a load factor α (alpha)?
31. Consider an algorithm that first sorts an array of `n` elements using Merge Sort (O(n log n)) and then iterates through the sorted array once (O(n)). What is the overall time complexity?
32. Which of the following statements about Theta (Θ) notation is FALSE?
33. Consider an algorithm that processes `n` items, and for each item, it performs a search operation that takes O(log n) time. The total number of operations is proportional to `n` times the cost of the search. What is the overall time complexity?
34. What is the worst-case time complexity for finding the minimum element in an unsorted array of `n` elements?
35. Consider the following code snippet: `for i in range(n): for j in range(n // 2): print(i, j)`. What is the Big-O complexity?
36. Which of the following Big-O complexities represents a cubic growth rate?
37. What is the best-case time complexity for searching an element in a Binary Search Tree (BST) with `n` nodes, if the tree is skewed (forming a linked list)?
38. An algorithm has a time complexity of O(n log n). If the input size `n` is multiplied by 4, by approximately what factor would the execution time increase?
39. Consider a binary search algorithm on a sorted array of size `n`. What is the best-case time complexity?
40. Consider an algorithm that performs a linear scan (O(n)) to find a specific element, and if found, it then performs a binary search (O(log n)) on a sub-array. What is the overall time complexity?
41. Which of the following data structures generally offers O(1) worst-case time complexity for insertion and deletion?
42. Consider an algorithm that processes `n` elements. For each element, it performs `k` operations, where `k` is a constant. The algorithm then performs a sorting step with complexity O(n log n). What is the overall time complexity?
43. What is the average-case time complexity of Quick Sort when using a randomized pivot selection strategy?
44. Consider the recursive function `T(n) = T(n-1) + O(1)`. What is its Big-O complexity?
45. If an algorithm has a time complexity of O(n^2), and the input size `n` is increased from 50 to 100, by approximately what factor would the execution time increase?
46. Which of the following Big-O complexities represents a linear growth rate?
47. Consider an algorithm that performs `n` operations, and for each operation, it calls another function that takes O(n) time. What is the overall time complexity?
48. What is the worst-case time complexity for insertion into a binary heap containing `n` elements?
49. Consider an algorithm that finds the maximum element in a sorted array of `n` elements. What is the time complexity?

Browse all average quizzes

More to play