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
logâ‚‚(n) + 1
n
1
Dynamic programming aims to reduce the time complexity of an algorithm by:
Storing the results of overlapping subproblems to avoid redundant computations
Dividing the problem into smaller subproblems and solving them recursively
Using a greedy approach to always make the locally optimal choice
Employing a divide-and-conquer strategy to break down the problem into smaller instances
What is the time complexity of searching for an element in an unsorted array of size 'n' in the worst-case scenario?
O(1)
O(log n)
O(n)
O(n^2)
What is the time complexity of Dijkstra's algorithm for finding the shortest path in a graph with V vertices and E edges using an adjacency list and a priority queue?
O(V^2)
O(V log E)
O(V + E)
O(E log V)
You have two algorithms for a task: Algorithm A with Θ(n) complexity and Algorithm B with O(n^2) complexity. Which statement is ALWAYS true?
Algorithm B might be faster for very small input sizes, but Algorithm A will eventually be faster as input grows.
Algorithm A and Algorithm B have the same efficiency in terms of time complexity.
It's impossible to compare the efficiency of the algorithms without knowing the exact implementation details.
Algorithm A will be faster than Algorithm B for all input sizes.
An algorithm processes an input of size 'n' by dividing it in half repeatedly until the size becomes 1. What is the most likely time complexity of this algorithm?
O(n log n)
Which of the following recurrence relations represents the time complexity of the merge sort algorithm?
T(n) = 2T(n/2) + O(n)
T(n) = T(n-1) + O(n)
T(n) = 2T(n-1) + O(1)
T(n) = T(n/2) + O(n)
Which of the following scenarios typically leads to an algorithm with linear time complexity, O(n)?
Calculating the Fibonacci sequence recursively.
Finding the smallest element in a max-heap.
Performing a linear search on a sorted array.
Traversing a binary tree.
What is the time complexity of inserting an element at the beginning of a singly linked list?
An algorithm has a time complexity of O(n log n). Which of the following statements is NOT necessarily true?
The algorithm will always be slower than an algorithm with O(n) complexity.
The algorithm's best-case runtime could be O(log n).
The algorithm's runtime grows at most as fast as n log n.
For large enough input sizes, the runtime is bounded above by some constant multiple of n log n.