Algorithm Complexity Flashcards

What does Big O notation represent?

Answer: The worst-case time complexity or upper bound of an algorithm's growth rate.

Big O notation is used to describe the upper bound of an algorithm's running time or space requirements in the worst-case scenario. It characterizes how the performance of an algorithm scales as the input size grows.

What is the time complexity of a binary search algorithm on a sorted array of size 'n'?

Answer: O(log n)

Binary search works by repeatedly dividing the search interval in half. This logarithmic behavior makes it highly efficient for searching in large, sorted datasets, as the number of comparisons grows very slowly with the input size 'n'.

A nested loop where the outer loop runs 'n' times and the inner loop also runs 'n' times for each outer iteration will typically have a time complexity of:

Answer: O(n^2)

For each of the 'n' iterations of the outer loop, the inner loop performs 'n' iterations. This results in a total of n * n = n^2 operations, leading to a quadratic time complexity.

Which of the following Big O notations represents the most efficient algorithm for a very large input size?

Answer: O(log n)

An algorithm with O(log n) complexity is the most efficient among the given options because its execution time grows the slowest as the input size 'n' increases. Logarithmic time is significantly better than linear, log-linear, or quadratic time for large inputs.

What is the time complexity for adding an element to the end of a dynamic array (like a vector in C++) in the amortized case?

Answer: O(1)

While a single add operation might occasionally take O(n) time if the array needs to be resized, these expensive operations are infrequent. When averaged over a long sequence of additions, the time complexity per operation is constant, or O(1) amortized.

An algorithm with a time complexity of O(1) is said to have:

Answer: Constant time complexity

O(1) signifies constant time complexity. This means the algorithm takes the same amount of time to execute, regardless of the size of the input data. Accessing an array element by its index is a classic example.

Consider the code: for (int i = 1; i < n; i = i * 2) { /* statement */ }. What is its time complexity?

Answer: O(log n)

In this loop, the iterator 'i' is doubled in each step (1, 2, 4, 8, ...). The loop stops when 'i' reaches 'n'. This pattern of repeated multiplication means the number of iterations is proportional to the logarithm (base 2) of n, resulting in O(log n) complexity.