Consider a binary search algorithm on a sorted array. In the worst-case scenario, how many comparisons are required to find a target element?
n/2
1
n
logâ‚‚(n) + 1
Dynamic programming aims to reduce the time complexity of an algorithm by:
Employing a divide-and-conquer strategy to break down the problem into smaller instances
Storing the results of overlapping subproblems to avoid redundant computations
Using a greedy approach to always make the locally optimal choice
Dividing the problem into smaller subproblems and solving them recursively
What is the time complexity of searching for an element in an unsorted array of size 'n' in the worst-case scenario?
O(log n)
O(n^2)
O(1)
O(n)
A linear search algorithm iterates through an unsorted array to find a target element. What is its average-case time complexity?
O(n²)
The Floyd-Warshall algorithm is used to find the shortest path between:
A vertex and all other vertices in a graph
None of the above
All pairs of vertices in a graph
Two specified vertices in a graph
Why is understanding time complexity crucial when comparing the efficiency of algorithms?
It provides a precise measurement of an algorithm's execution time in milliseconds.
It helps determine the exact amount of memory an algorithm will use.
It reveals the underlying hardware limitations that affect algorithm performance.
It allows us to analyze how the algorithm's runtime changes relative to the input size.
What does it mean for an algorithm to have a time complexity of Θ(1)?
The runtime is constant and independent of the input size.
The algorithm is guaranteed to be the fastest possible solution for the problem.
The runtime grows linearly with the input size.
The algorithm's runtime is unpredictable and varies greatly with different inputs.
Which of the following is NOT a common reason why real-world performance might differ from theoretical time complexity analysis?
The specific hardware being used
The choice of algorithm used
Caching and data locality
The programming language and compiler optimizations
Consider an algorithm with a best-case time complexity of O(1) and a worst-case time complexity of O(n). Which of the following statements is ALWAYS true?
The average-case time complexity is also O(n).
The algorithm's performance is independent of the input data.
The algorithm will always have a time complexity of O(1) or O(n).
The algorithm's time complexity cannot be determined solely from the best- and worst-case scenarios.
Which of the following has a time complexity of O(n^2) in its worst-case scenario?
Heap Sort
QuickSort
Merge Sort
Bubble Sort