Which of the following scenarios typically leads to an algorithm with linear time complexity, O(n)?
Traversing a binary tree.
Finding the smallest element in a max-heap.
Performing a linear search on a sorted array.
Calculating the Fibonacci sequence recursively.
Which of the following recurrence relations represents the time complexity of the merge sort algorithm?
T(n) = 2T(n-1) + O(1)
T(n) = T(n-1) + O(n)
T(n) = T(n/2) + O(n)
T(n) = 2T(n/2) + O(n)
Which of the following sorting algorithms has the best average-case time complexity?
Insertion Sort
Merge Sort
Selection Sort
Bubble Sort
If an algorithm has a time complexity of Ω(n log n), what can you conclude about its best-case runtime?
It will always be slower than an algorithm with O(n^2) time complexity.
It will always be faster than an algorithm with O(n) time complexity.
It will have a constant runtime regardless of input size.
It cannot be faster than an algorithm with O(log n) time complexity.
What is the time complexity of inserting an element at the beginning of a singly linked list?
O(n)
O(1)
O(n log n)
O(log n)
An algorithm has a time complexity of O(n log n). Which of the following statements is NOT necessarily true?
The algorithm's runtime grows at most as fast as n log n.
The algorithm will always be slower than an algorithm with O(n) complexity.
For large enough input sizes, the runtime is bounded above by some constant multiple of n log n.
The algorithm's best-case runtime could be O(log n).
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 algorithm will always have a time complexity of O(1) or O(n).
The algorithm's performance is independent of the input data.
The algorithm's time complexity cannot be determined solely from the best- and worst-case scenarios.
The average-case time complexity is also 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²)
What does it mean for an algorithm to have a time complexity of Θ(1)?
The algorithm is guaranteed to be the fastest possible solution for the problem.
The algorithm's runtime is unpredictable and varies greatly with different inputs.
The runtime is constant and independent of the input size.
The runtime grows linearly with the input size.
Which of the following has a time complexity of O(n^2) in its worst-case scenario?
Heap Sort
QuickSort