Which of the following asymptotic notations represents the tightest upper bound on the growth of a function?
Big-O (O)
Big Omega (Ω)
Little-o (o)
Big Theta (Θ)
Which data structure, when used for searching, can potentially improve the time complexity from O(n) to O(log n)?
Queue
Array
Binary Tree
Linked List
What is the time complexity of searching for an element in a sorted array using binary search?
O(n log n)
O(log n)
O(1)
O(n)
In what scenario might an algorithm with a worse theoretical time complexity perform better in practice than one with a better complexity?
All of the above.
When the algorithm with worse complexity is implemented in a more efficient programming language.
When the algorithm with better complexity has a very large constant factor hidden in its Big O notation.
When the input data size is very small.
What is the worst-case time complexity of the linear search algorithm?
What is the time complexity of finding the Fibonacci number at position n using a recursive approach without memoization?
O(n^2)
O(2^n)
Which notation is most useful when analyzing the average-case time complexity of an algorithm, considering all possible inputs?
All notations are equally useful for average-case analysis.
Which of the following is a limitation of time complexity analysis?
It can't be applied to algorithms with nested loops
It's only relevant for algorithms processing numerical data
It always provides the exact runtime of an algorithm
It doesn't consider the hardware on which the algorithm will run
Which searching algorithm has a time complexity of O(log n) in the average case?
Binary Search
Linear Search
Jump Search
Interpolation Search
What does an algorithm with a time complexity of O(n) signify?
The runtime is unpredictable
The runtime increases exponentially with the input size
The runtime is constant regardless of input size
The runtime increases linearly with the input size