Consider a binary search algorithm on a sorted array. In the worst-case scenario, how many comparisons are required to find a target element?
n
n/2
logâ‚‚(n) + 1
1
You need to design an algorithm that operates on a very large dataset. Which time complexity should you aim for to ensure reasonable performance?
O(2^n)
O(log n)
O(n!)
O(n^3)
What is the Big-O notation of an algorithm that iterates through an array of size 'n' twice in nested loops?
O(n^2)
O(1)
O(n)
Which of the following statements about the relationship between theoretical time complexity and real-world performance is FALSE?
Constant factors and lower-order terms ignored in Big O notation can significantly impact real-world performance.
Hardware characteristics like CPU speed and cache size can influence the actual runtime of an algorithm.
An algorithm with better theoretical complexity will always outperform an algorithm with worse complexity in practice.
Real-world data often exhibits patterns that can be exploited to improve performance beyond theoretical predictions.
What is the time complexity of calculating the nth Fibonacci number using the dynamic programming approach?
O(n log n)
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?
Algorithm B might be faster for very small input sizes, but Algorithm A will eventually be faster as input grows.
It's impossible to compare the efficiency of the algorithms without knowing the exact implementation details.
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 Floyd-Warshall algorithm is used to find the shortest path between:
Two specified vertices in a graph
A vertex and all other vertices in a graph
All pairs of vertices in a graph
None of the above
What does it mean for an algorithm to have a time complexity of Θ(1)?
The runtime is constant and independent of the input size.
The algorithm's runtime is unpredictable and varies greatly with different inputs.
The runtime grows linearly with the input size.
The algorithm is guaranteed to be the fastest possible solution for the problem.
Which of the following sorting algorithms has the best average-case time complexity?
Bubble Sort
Merge Sort
Selection Sort
Insertion Sort
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(E log V)
O(V^2)
O(V + E)
O(V log E)