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 have two algorithms, A and B, for the same problem. A has a time complexity of O(n log n) and Ω(n), while B has a time complexity of O(n^2) and Ω(log n). Which of the following statements is always true?
Algorithm B is faster than Algorithm A for all input sizes.
We cannot definitively compare the performance of the two algorithms based on the given information.
Algorithm A is faster than Algorithm B for all input sizes.
Algorithm A is faster than Algorithm B for sufficiently large input sizes.
You are comparing two sorting algorithms: Algorithm X with O(n log n) average-case complexity and Algorithm Y with O(n^2) worst-case complexity. In your benchmarks, Algorithm Y consistently outperforms Algorithm X. What is a PLAUSIBLE explanation for this observation?
Algorithm Y is inherently more efficient than Algorithm X for all input sizes and distributions.
The benchmark is flawed and does not accurately measure the execution time of the algorithms.
The input data, despite being randomly generated, consistently represents a special case where Algorithm Y excels.
The input data used in the benchmark always triggers the worst-case scenario for Algorithm X.
An algorithm processes an input array of size 'n'. It iterates through the array once, performing constant-time operations for each element. Inside the loop, it calls a helper function that has a time complexity of Θ(log n). What is the overall time complexity of this algorithm?
O(n^2)
Why is time complexity generally considered more important than space complexity in algorithm analysis?
Space complexity cannot be expressed using Big-O notation.
Space complexity is irrelevant in modern computing.
Time complexity is always more difficult to analyze.
Modern computers have abundant memory, while efficient time utilization often remains a bottleneck.
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?
Insufficient information to determine
Algorithm B
Both are equally preferable
Algorithm A
Which notation is most appropriate to describe the best-case time complexity of an algorithm where the input size doesn't affect the running time?
Big-Omega (Ω)
Little-omega (ω)
Big-O (O)
Big-Theta (Θ)
Which of the following is the LEAST reliable indicator of an algorithm's real-world performance?
Profiling results on a representative dataset
Worst-case time complexity
Average-case time complexity
Benchmarking results on different hardware configurations
Which statement about benchmarking is TRUE?
Benchmarking is primarily used for comparing the theoretical time complexity of different algorithms.
Benchmarking results are always generalizable across different hardware and software environments.
Benchmarking is only useful for large-scale applications and not for smaller projects.
Benchmarking focuses on measuring the execution time of an algorithm in a controlled environment.
An algorithm performs the following operations: it iterates through an array of size n, and for each element, it performs a binary search on a sorted array of size m. What is the overall time complexity of the algorithm?
O(n * m)
O(m log n)
O(n + log m)
O(n log m)