01 Algorithm Analysis and Big-O Notation Free Online FlashCards

What is an algorithm?

An algorithm is a finite, precise sequence of steps that transforms input into output to solve a problem.

What does an abstract data type specify?

An ADT specifies the values and operations a type supports without prescribing how those operations are implemented.

What is a representation invariant?

A representation invariant is a condition that must remain true about a data structure’s internal state.

Which elements commonly support a correctness argument?

A correctness proof uses a precondition, postcondition, invariant, and termination argument to show that an algorithm produces the required result and stops.

What are the three steps for proving a loop invariant?

The three loop-invariant steps are initialization, maintenance, and termination.

Why must input size be defined precisely?

The input-size variable depends on the problem: it may count array elements, string characters, tree nodes, graph vertices, edges, or integer-representation bits.

What does time complexity measure?

Time complexity describes how the number of basic operations grows with input size; it does not usually predict exact elapsed seconds.

What does worst-case complexity measure?

Worst-case analysis measures the greatest work for any input of size $n$, providing a guarantee for every input of that size.

What is auxiliary space?

Auxiliary space is the additional memory used by an algorithm beyond the memory needed to store its input.

What does Big-O notation express?

Big-O gives an eventual asymptotic upper bound: for suitable constants $c>0$ and $n_0$, $0\le f(n)\le c\,g(n)$ for all $n\ge n_0$.

When is a function $\Theta(g(n))$?

A function is $\Theta(g(n))$ when it is both $O(g(n))$ and $\Omega(g(n))$, giving an asymptotically tight bound.

How do common growth classes rank from slower to faster?

From slower to faster growth, the listed classes are $\Theta(1)$, $\Theta(\log n)$, $\Theta(n)$, $\Theta(n\log n)$, $\Theta(n^2)$, $\Theta(2^n)$, and $\Theta(n!)$.