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 grows at least as fast as a linear function.
It cannot have a constant upper bound.
It could take constant time in the best case.
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(n log n)
O(1)
Which of the following notations provides the tightest possible bound on the growth rate of an algorithm's running time?
Big-O (O)
Little-o (o)
Big-Omega (Ω)
Big-Theta (Θ)
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 self-balancing binary search tree
A standard binary search tree
A hash table
A sorted array
Which of these is NOT a valid use of time complexity analysis?
Choosing between different data structures for a specific task.
Determining the exact execution time of an algorithm on a given hardware.
Comparing the scalability of different algorithms as data size increases.
Identifying potential performance bottlenecks in a large codebase.
Which of the following operations generally exhibits O(log n) time complexity in a balanced binary search tree?
Calculating the height of the tree
Printing all elements in sorted order
Finding the minimum element
Inserting a new element
An algorithm processes an input list of size n. It first performs an O(n log n) sorting operation. Then, for each element in the sorted list, it performs a nested loop iterating over all pairs of elements in the list. What is the overall time complexity of this algorithm?
O(n^2 log n)
O(n^2)
O(n^3)
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 (ω)
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 + k log n)
O(k^2)
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 all input sizes.
Algorithm A is faster than Algorithm B for sufficiently large input sizes.
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.