What is the time complexity of the following code snippet?
def mystery(n): if n <= 1: return 1 return mystery(n-1) + mystery(n-2)
O(2^n)
O(n)
O(n log n)
O(log n)
You need to choose an algorithm for a real-time system with strict timing constraints. Algorithm X has a time complexity of O(n log n) in the worst case and Θ(1) in the best case. Algorithm Y has a time complexity of Θ(n) in all cases. Which algorithm is a safer choice and why?
Algorithm Y, because its time complexity is consistent and predictable.
Neither algorithm is suitable for a real-time system.
Both algorithms are equally suitable for a real-time system.
Algorithm X, because its best-case complexity is excellent.
Which of the following notations provides the tightest possible bound on the growth rate of an algorithm's running time?
Little-o (o)
Big-Omega (Ω)
Big-Theta (Θ)
Big-O (O)
An algorithm has a time complexity of ω(n). Which of the following statements is definitely false about its running time?
It might have a logarithmic component in its runtime.
It could take constant time in the best case.
It cannot have a constant upper bound.
It grows at least as fast as a linear function.
You need to sort a large dataset. Algorithm A has a time complexity of O(n log n) and a space complexity of O(1). Algorithm B has a time complexity of O(n) but requires O(n) extra space. Which algorithm is preferable if memory usage is severely constrained?
Algorithm A
Algorithm B
Both are equally preferable
Insufficient information to determine
You need to find the smallest k elements in an unsorted array of size n. What is the most efficient time complexity achievable in the average case?
O(n^2)
O(n + k log n)
O(k^2)
A randomized algorithm has a worst-case running time of O(n^2), but its expected running time is O(n log n). What does this imply about the algorithm's performance?
The algorithm's running time is independent of the input.
The algorithm is unsuitable for practical use due to its unpredictable running time.
The algorithm always runs in O(n log n) time.
On average, the algorithm performs better than its worst-case bound.
You are designing a system to handle real-time stock market data. Which of the following time complexities would be LEAST desirable for an algorithm processing incoming price updates?
O(1)
You are given a sorted array of n integers. You want to determine if there exists a pair of elements in the array that sum up to a specific target value. Which algorithm provides the most efficient time complexity?
Using a hash table to store seen elements
Sorting the array and then using binary search
Nested loops to check all pairs
Using two pointers, one at the beginning and one at the end of the array
When optimizing code for better time complexity, which approach will NOT always lead to improved real-world performance?
Caching frequently accessed data to avoid recomputation.
Using a more complex data structure with better time complexity for certain operations.
Reducing the number of operations within loops.
Replacing an O(n^2) algorithm with an O(n log n) algorithm.