Big O notation measures the upper bound of an algorithm’s runtime in the worst-case scenario. It helps analyze how the algorithm’s performance scales with larger input sizes, providing insight into its efficiency.
Which algorithm is used for finding the minimum spanning tree in a graph?
A Dijkstra’s Algorithm
B Bellman-Ford
C Prim’s Algorithm
D Floyd-Warshall
Prim’s algorithm is a greedy algorithm used to find the minimum spanning tree of a graph. It starts with an arbitrary vertex and grows the tree by adding the smallest edge that connects a vertex in the tree to one outside it.
Which time complexity does Merge Sort have?
A O(n^2)
B O(n log n)
C O(n)
D O(log n)
Merge Sort divides the array into two halves, recursively sorts each half, and then merges them. Its time complexity is O(n log n) for all cases, making it efficient for large data sets.
What does space complexity refer to?
A Memory required by algorithm
B Time taken by algorithm
C Input size
D Worst-case time
Space complexity measures the total memory space an algorithm needs to run as a function of the input size. It includes both the memory for input storage and extra space used during computation.
Which algorithm is typically used for shortest path calculation in weighted graphs?
A Merge Sort
B Quick Sort
C Bellman-Ford
D Binary Search
The Bellman-Ford algorithm is used to find the shortest paths from a single source vertex to all other vertices in a graph, even if the graph contains negative-weight edges.
What is the best-case time complexity of Binary Search?
A O(n)
B O(log n)
C O(n log n)
D O(1)
In Binary Search, the search interval is halved with each step, so the best-case time complexity occurs when the target element is found in the first comparison, which is O(1). In general, it is O(log n).
What is the characteristic of a backtracking algorithm?
A Always finds optimal solutions
B Avoids recursion
C Focuses on greedy choices
D Explores all possible solutions
Backtracking algorithms explore all possible solutions systematically, making choices and “backtracking” when they reach a dead end. This approach is used for problems like the N-Queens and Sudoku puzzles.
What does the term “NP-Hard” refer to?
A Problems at least as hard as NP-complete
B Problems solvable in polynomial time
C Problems with exponential time complexity
D Problems not in NP
NP-Hard problems are problems that are at least as hard as the hardest problems in NP. These problems are not necessarily in NP, and no polynomial-time solution is known for them.
Which of the following sorting algorithms is not stable?
A Merge Sort
B Insertion Sort
C Quick Sort
D Bubble Sort
Quick Sort is not a stable sorting algorithm because it can change the relative order of equal elements during the partitioning process. On the other hand, Merge Sort and Insertion Sort are stable.
Which type of algorithm is used for finding the longest common subsequence?
A Divide and conquer
B Greedy algorithm
C Brute force
D Dynamic programming
The longest common subsequence (LCS) problem is solved using dynamic programming. This method stores results of subproblems to avoid redundant calculations and ensures efficient computation of LCS.
What is the primary advantage of a greedy algorithm?
A Simple to implement
B Always gives optimal solution
C Requires no recursion
D Always faster than other algorithms
Greedy algorithms are simple because they make locally optimal choices at each step. However, they do not always produce the optimal solution for every problem. Their simplicity makes them efficient for certain problems.
What is the time complexity of an insertion sort algorithm in the worst case?
A O(n log n)
B O(n)
C O(n^2)
D O(log n)
Insertion sort has a worst-case time complexity of O(n^2) because, in the worst case, each element has to be compared and shifted through the entire sorted portion of the array.
Which algorithm is best suited for solving problems involving optimal substructure?
A Greedy algorithms
B Dynamic programming
C Divide and conquer
D Randomized algorithms
Dynamic programming is best suited for problems with optimal substructure, where the solution to a problem can be built from solutions to smaller subproblems, like the Fibonacci sequence or the knapsack problem.
Which of the following is true about Dijkstra’s algorithm?
A Works for negative edges
B Solves the maximum flow problem
C Uses backtracking
D Solves the shortest path problem
Dijkstra’s algorithm is used to solve the shortest path problem in graphs with non-negative edge weights. It works by greedily selecting the closest vertex to the source vertex until the shortest path to all vertices is found.
What is the best sorting algorithm for a small dataset?
A Bubble Sort
B Quick Sort
C Merge Sort
D Heap Sort
Bubble Sort is generally not efficient for large datasets, but it can be quite effective for small datasets due to its simplicity. It compares adjacent elements and swaps them until the array is sorted.