07 — Efficiency and Computational Complexity Free Online FlashCards

What is an algorithm?

An algorithm is a precisely specified procedure that produces a result from an input.

What does n represent in complexity analysis?

Input size is the quantity used to describe how large an instance is; for an array it may be the number of elements, while a graph may use |V| and |E|.

What does time complexity measure?

Time complexity describes how an algorithm’s required computational work grows as the input becomes larger, rather than stating a fixed elapsed time.

What is auxiliary space?

Auxiliary space is the additional memory an algorithm uses beyond the memory already required to store its input.

What condition does binary search require?

Binary search requires a sorted array because it decides which half of the remaining interval can be discarded.

What is the typical complexity of indexed array access?

Accessing an array element by index has Θ(1) time complexity because the operation takes constant time under the stated computational model.

What does f(n) = O(g(n)) mean?

Big-O notation gives an asymptotic upper bound: beyond some input size, f(n) grows no faster than a constant multiple of g(n).

What does f(n) = Ω(g(n)) mean?

Big-Omega notation gives an asymptotic lower bound: beyond some input size, f(n) grows at least as quickly as a constant multiple of g(n).

What does f(n) = Θ(g(n)) mean?

Big-Theta notation gives an asymptotically tight bound: f(n) is bounded both above and below by constant multiples of g(n).

What is linear search’s best-case complexity?

For linear search, the best case is Θ(1): the target is found at the first position, so only a constant amount of work is needed.

What must average-case analysis specify?

Average-case analysis requires a specified input distribution. If a target is equally likely at any position, successful linear search examines about (n+1)/2 elements on average.

What is the complexity of two full nested loops?

Two nested loops that each run n times perform n × n constant-time operations, giving Θ(n²) running time.