Big O notation represents the upper bound of an algorithm’s time complexity. It describes the worst-case scenario of an algorithm’s performance, helping to understand how it scales with input size.
What is the time complexity of Bubble Sort in the worst case?
A O(n²)
B O(n)
C O(n log n)
D O(log n)
In the worst case, Bubble Sort has a time complexity of O(n²). It compares and swaps adjacent elements repeatedly, which leads to quadratic time complexity when the list is sorted in reverse order.
What is the space complexity of Quick Sort?
A O(n)
B O(log n)
C O(1)
D O(n log n)
Quick Sort has a space complexity of O(1) when implemented iteratively. The space complexity depends on the algorithm’s partitioning approach, which can be done in-place without requiring additional space.
What does Theta notation represent?
A Worst case
B Exact bound
C Lower bound
D Upper bound
Theta notation represents the exact asymptotic behavior of an algorithm, providing both upper and lower bounds for the time complexity. It indicates the precise rate at which the algorithm’s running time grows with input size.
Which algorithm is an example of Divide and Conquer?
A Merge Sort
B Binary Search
C Quick Sort
D All of the above
Merge Sort, Binary Search, and Quick Sort all use the divide and conquer strategy. They divide a problem into smaller subproblems, solve them recursively, and then combine the results to solve the overall problem.
Which of these is an optimal solution for the Knapsack problem?
A Dynamic Programming
B Backtracking
C Greedy Algorithm
D Brute Force
The Knapsack problem is solved optimally using dynamic programming. It stores the results of overlapping subproblems and avoids redundant calculations, making it much more efficient than brute force or greedy algorithms.
Which of these algorithms is used to find the shortest path in a graph?
A Heap Sort
B Binary Search
C Dijkstra’s Algorithm
D Merge Sort
Dijkstra’s algorithm is used to find the shortest path from a source vertex to all other vertices in a graph with non-negative edge weights. It is a greedy algorithm that selects the next closest vertex at each step.
What is the time complexity of Merge Sort?
A O(n)
B O(n²)
C O(n log n)
D O(log n)
Merge Sort has a time complexity of O(n log n) in all cases. It divides the input into two halves, recursively sorts them, and merges them back together, resulting in efficient sorting even for large datasets.
What does the “Omega” notation describe?
A Worst case
B Upper bound
C Best case
D Exact bound
Omega notation is used to describe the lower bound of an algorithm’s time complexity. It defines the best-case performance, or the minimum time required by an algorithm for an input of size n.
What is the primary feature of Greedy algorithms?
A Makes locally optimal choices
B Solves all problems optimally
C Guarantees exact solutions
D Uses dynamic programming
Greedy algorithms make locally optimal choices at each step, aiming for a global optimum. However, they do not always guarantee the best solution for all problems, such as in the case of the Knapsack problem.
Which of the following algorithms is used to find the longest common subsequence?
A Merge Sort
B Dynamic Programming
C Quick Sort
D Binary Search
The Longest Common Subsequence (LCS) problem is solved using dynamic programming. The algorithm builds a solution incrementally, storing intermediate results to avoid redundant calculations and ensuring efficient computation.
Which of the following problems is NP-Complete?
A Longest Path Problem
B Binary Search
C Sorting an array
D Matrix multiplication
The Longest Path Problem is NP-Complete because no polynomial-time algorithm is known to solve it efficiently. It involves finding the longest simple path between two vertices in a graph, which is computationally difficult.
Which algorithm is used for binary search in a sorted array?
A Heap Sort
B Merge Sort
C Binary Search
D Quick Sort
Binary Search is an efficient algorithm used to find an element in a sorted array by repeatedly dividing the search interval in half. It has a time complexity of O(log n) and is much faster than linear search.
What is the time complexity of Insertion Sort in the worst case?
A O(n log n)
B O(n)
C O(log n)
D O(n²)
Insertion Sort has a worst-case time complexity of O(n²), which occurs when the array is sorted in reverse order. It repeatedly shifts elements to the right to insert the current element into its correct position.
What is the space complexity of Binary Search?
A O(n)
B O(n log n)
C O(log n)
D O(1)
Binary Search has a space complexity of O(1) because it operates in-place and does not require additional memory beyond a few variables to track the search interval. This makes it very space-efficient.