1 Algorithm Analysis and Big-O Notation Free Online FlashCards

What is an algorithm?

An algorithm is a finite, precisely defined sequence of steps for solving a problem.

How do an ADT and data structure differ?

An ADT specifies values and permitted operations without describing implementation; a data structure is the concrete representation that implements it.

What does input size $n$ measure?

Input size is the measure of problem scale, such as the number of array elements, string characters, graph vertices, or representation bits.

What is a cost model?

A cost model identifies which operations count as basic units of work, often treating arithmetic, assignment, comparison, and array access as constant-time.

What are the time and auxiliary space costs of summing an array?

The sum loop has runtime $\Theta(n)$ because it processes each element once, and auxiliary space $\Theta(1)$ because it uses only a fixed amount of extra memory.

What is the complexity of two nested $n$-iteration loops?

Two independent nested loops that each run $n$ times perform $\Theta(n^2)$ work because the iteration counts multiply.

What is auxiliary space?

Auxiliary space is memory used beyond the input; total space includes both the input storage and the algorithm’s additional memory.

What are sequential search’s best and worst cases?

For sequential search, the best case is $\Theta(1)$, while the worst case is $\Theta(n)$ when the target is last or absent.

What does Big-O notation express?

Big-O is an asymptotic upper bound: eventually, $T(n)\leq c f(n)$ for positive constants $c$ and $n_0$.

When is $\Theta(f(n))$ appropriate?

Big-$\Theta$ is a tight asymptotic bound because the function is both an asymptotic upper bound and an asymptotic lower bound.

How is a runtime expression simplified asymptotically?

To simplify an asymptotic expression, remove constant multipliers and retain the fastest-growing term; thus $4n^2+3n+9=\Theta(n^2)$.

Why is binary search $\Theta(\log n)$?

Binary search has runtime $\Theta(\log n)$ because each step halves the remaining input, giving the recurrence $T(n)=T(n/2)+\Theta(1)$.