Which of the following is NOT a common reason why real-world performance might differ from theoretical time complexity analysis?
The programming language and compiler optimizations
The specific hardware being used
Caching and data locality
The choice of algorithm used
Dynamic programming aims to reduce the time complexity of an algorithm by:
Dividing the problem into smaller subproblems and solving them recursively
Storing the results of overlapping subproblems to avoid redundant computations
Using a greedy approach to always make the locally optimal choice
Employing a divide-and-conquer strategy to break down the problem into smaller instances
If an algorithm has a time complexity of Ω(n log n), what can you conclude about its best-case runtime?
It will have a constant runtime regardless of input size.
It will always be slower than an algorithm with O(n^2) time complexity.
It will always be faster than an algorithm with O(n) time complexity.
It cannot be faster than an algorithm with O(log n) time complexity.
The Floyd-Warshall algorithm is used to find the shortest path between:
None of the above
Two specified vertices in a graph
All pairs of vertices in a graph
A vertex and all other vertices in a graph
You have two algorithms for a task: Algorithm A with Θ(n) complexity and Algorithm B with O(n^2) complexity. Which statement is ALWAYS true?
It's impossible to compare the efficiency of the algorithms without knowing the exact implementation details.
Algorithm B might be faster for very small input sizes, but Algorithm A will eventually be faster as input grows.
Algorithm A will be faster than Algorithm B for all input sizes.
Algorithm A and Algorithm B have the same efficiency in terms of time complexity.
The Master Theorem is used to solve recurrence relations of a specific form. Which of the following forms is NOT suitable for the Master Theorem?
T(n) = aT(n-b) + f(n)
T(n) = aT(n/b) + f(n)
T(n) = √n * T(√n) + n
All of the above are suitable for the Master Theorem
What is the time complexity of inserting an element at the beginning of a singly linked list?
O(n log n)
O(n)
O(1)
O(log n)
Which of the following recurrence relations represents the time complexity of the merge sort algorithm?
T(n) = T(n-1) + O(n)
T(n) = 2T(n-1) + O(1)
T(n) = 2T(n/2) + O(n)
T(n) = T(n/2) + O(n)
What is the time complexity of Dijkstra's algorithm for finding the shortest path in a graph with V vertices and E edges using an adjacency list and a priority queue?
O(V + E)
O(E log V)
O(V log E)
O(V^2)
A linear search algorithm iterates through an unsorted array to find a target element. What is its average-case time complexity?
O(n²)