Big O notation is used to describe the upper bound of an algorithm’s runtime, focusing on the worst-case scenario. It helps measure how the time complexity increases as the input size grows.
What is the time complexity of Merge Sort?
A O(n log n)
B O(log n)
C O(n)
D O(n²)
Merge Sort has a time complexity of O(n log n) in all cases (best, worst, and average). It splits the array into halves and recursively sorts them, which results in efficient performance.
What is the primary use of a greedy algorithm?
A To solve NP-Complete problems
B To make locally optimal choices
C To find optimal solutions
D To find exact solutions
Greedy algorithms make locally optimal choices at each step with the hope of finding a global optimum. While effective for some problems like the knapsack problem, they don’t always guarantee the best solution.
Which of the following is used for finding the shortest path in a weighted graph?
A Binary Search
B Merge Sort
C Heap Sort
D Dijkstra’s
Dijkstra’s algorithm is used to find the shortest path from a source node to all other nodes in a weighted graph. It works by greedily selecting the node with the smallest tentative distance.
What is the space complexity of the Merge Sort algorithm?
A O(n log n)
B O(n)
C O(n²)
D O(1)
Merge Sort has a space complexity of O(n) because it requires additional space for the temporary arrays used during the merge process. This extra space grows with the size of the input.
What is the worst-case time complexity of Quick Sort?
A O(log n)
B O(n)
C O(n²)
D O(n log n)
In the worst case, Quick Sort has a time complexity of O(n²), which occurs when the pivot is poorly chosen (e.g., when the array is already sorted). This results in unbalanced partitioning.
What is a key feature of dynamic programming?
A Always uses brute force
B Recursively solves overlapping subproblems
C Focuses on greedy choices
D Solves problems in one step
Dynamic programming solves problems by breaking them into smaller overlapping subproblems and storing their solutions to avoid redundant work. This approach is used in problems like the Fibonacci sequence and shortest paths.
What does the “Theta” notation describe?
A Worst-case scenario
B Upper bound
C Exact asymptotic behavior
D Lower bound
Theta notation provides the exact asymptotic complexity of an algorithm. It describes both the upper and lower bounds of an algorithm’s performance, indicating its precise rate of growth with respect to the input size.
What is the main goal of backtracking algorithms?
A To explore all potential solutions
B To find the best solution
C To find a random solution
D To minimize space complexity
Backtracking algorithms systematically explore all possible solutions to a problem. They build partial solutions and backtrack whenever they reach a point where no solution is possible, ensuring all possibilities are considered.
What is the worst-case time complexity of Binary Search?
A O(1)
B O(n log n)
C O(n)
D O(log n)
Binary Search works by repeatedly dividing the search interval in half. In the worst case, it reduces the search space logarithmically, making its time complexity O(log n), which is much faster than linear search.
Which algorithm is used for pattern matching in strings?
A Merge Sort
B Quick Sort
C KMP
D Dijkstra’s
The Knuth-Morris-Pratt (KMP) algorithm is used for string matching. It improves on brute force by preprocessing the pattern to create a partial match table, allowing it to skip unnecessary comparisons during the search.
What is the primary feature of a hashing algorithm?
A To analyze patterns
B To map data to fixed-size values
C To find duplicates
D To sort data
A hashing algorithm maps input data (like strings or numbers) to fixed-size values, known as hash values. This makes data retrieval efficient, as it can be accessed directly using the hash.
Which of these is an example of a NP-Complete problem?
A Binary Search
B Sorting
C Traveling Salesman Problem
D Finding the shortest path
The Traveling Salesman Problem (TSP) is an NP-Complete problem, which means it is both in NP and as hard as any problem in NP. Solving it in polynomial time would solve all NP problems efficiently.
What is the main principle behind Divide and Conquer algorithms?
A Break a problem into smaller parts and solve recursively
B Optimize by selecting the best option
C Solve the problem without recursion
D Always find the minimum solution
Divide and conquer algorithms solve problems by breaking them into smaller subproblems, solving each subproblem recursively, and combining the results. This approach is used in algorithms like Merge Sort and Quick Sort.
Which algorithm is used to solve the Longest Common Subsequence problem?
A Merge Sort
B Quick Sort
C Binary Search
D Dynamic Programming
The Longest Common Subsequence (LCS) problem is solved using dynamic programming. The algorithm builds a solution incrementally by solving subproblems and storing intermediate results to avoid redundant calculations.