The statement 'f(n) = o(g(n))' implies which of the following?
f(n) and g(n) have the same growth rate.
f(n) is asymptotically slower than g(n) as n approaches infinity.
f(n) is always strictly slower than g(n) for all values of n.
g(n) is an upper bound, but not necessarily a tight bound, for f(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.
Algorithm A is faster than Algorithm B for all input sizes.
Algorithm A is faster than Algorithm B for sufficiently large input sizes.
We cannot definitively compare the performance of the two algorithms based on the given information.
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 is unsuitable for practical use due to its unpredictable running time.
On average, the algorithm performs better than its worst-case bound.
The algorithm always runs in O(n log n) time.
The algorithm's running time is independent of the input.
A recursive function has a base case that executes in O(1) time. For each recursive step, it makes 3 recursive calls with input size n/2. What is the overall time complexity of this function?
O(n^log_2(3))
O(n)
O(n^2)
O(n log n)
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?
Sorting the array and then using binary search
Using two pointers, one at the beginning and one at the end of the array
Nested loops to check all pairs
Using a hash table to store seen elements
Consider a dynamic array implementation where resizing to double the capacity takes O(n) time. If we perform 'n' insertions sequentially, what is the amortized time complexity per insertion?
O(log n)
O(1)
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
Benchmarking results on different hardware configurations
Average-case time complexity
What is the time complexity of inserting an element at the beginning of a dynamically sized array that needs to resize by doubling its capacity when full?
An algorithm has a time complexity of ω(n). Which of the following statements is definitely false about its running time?
It cannot have a constant upper bound.
It could take constant time in the best case.
It might have a logarithmic component in its runtime.
It grows at least as fast as a linear function.
You are designing a data structure that supports two operations: 'insert' and 'find median'. 'Insert' adds an element in O(log n) time. Which of the following allows the 'find median' operation to also be achieved in O(log n) time?
A standard binary search tree
A sorted array
A self-balancing binary search tree
A hash table