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(n log m)
O(m log n)
O(n + log m)
The statement 'f(n) = o(g(n))' implies which of the following?
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.
f(n) and g(n) have the same growth rate.
g(n) is an upper bound, but not necessarily a tight bound, for f(n).
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?
O(n)
O(log n)
O(1)
O(n log n)
Why is time complexity generally considered more important than space complexity in algorithm analysis?
Modern computers have abundant memory, while efficient time utilization often remains a bottleneck.
Space complexity is irrelevant in modern computing.
Time complexity is always more difficult to analyze.
Space complexity cannot be expressed using Big-O notation.
Consider a nested loop structure where the outer loop runs n times and the inner loop runs from 1 to i, where 'i' is the current iteration of the outer loop. What is the total number of iterations of the inner loop?
n^2
n
log n
n(n+1)/2
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^2)
O(n^log_2(3))
Which of these is NOT a valid use of time complexity analysis?
Comparing the scalability of different algorithms as data size increases.
Choosing between different data structures for a specific task.
Identifying potential performance bottlenecks in a large codebase.
Determining the exact execution time of an algorithm on a given hardware.
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?
Little-omega (ω)
Big-O (O)
Big-Theta (Θ)
Big-Omega (Ω)
A hash table using open addressing has a load factor of 0.8. What is the expected average-case time complexity for a successful search operation?
It depends on the hash function
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 A is faster than Algorithm B for sufficiently large input sizes.
Algorithm A is faster than Algorithm B for all input sizes.
We cannot definitively compare the performance of the two algorithms based on the given information.
Algorithm B is faster than Algorithm A for all input sizes.