Analysis of Algorithms

Flashcards about the analysis of algorithms, mathematical models, order of growth, and memory usage.

What is the primary practical reason to analyze algorithms?

Avoid performance bugs.

What steps are involved in the scientific method applied to algorithm analysis?

Observe, hypothesize, predict, verify, and validate.

What is the 3-SUM problem?

Given N distinct integers, find how many triples sum to exactly zero.

What is the purpose of the doubling hypothesis?

To quickly estimate 'b' in a power-law relationship by running a program and doubling the input size.

What are the system-independent effects on experimental algorithmics?

Algorithm and input data.

What does total running time consist of?

The sum of (cost × frequency) for all operations.

What is cost model?

Use some basic operation as a proxy for running time.

What is considered to be the order of growth of f(N)?

If f(N) ~ c g(N) for some constant c > 0, then the order of growth of f(N) is g(N).

Name some common order-of-growth classifications.

1, log N, N, N log N, N^2, N^3, and 2^N

What is the strategy behind binary search?

Compare key against middle entry; if too small, go left; if too big, go right; if equal, found.

What is the best-case scenario in types of analysis?

Lower bound on cost, determined by the 'easiest' input.

Define Big Theta Notation

Asymptotic order of growth

Define Big Oh Notation

Θ(N^2) and smaller; used to develop upper bounds.

Define Big Omega Notation

Θ(N^2) and larger; used to develop lower bounds.

What is examined to analyze memory?

Bits, Bytes, Megabytes, and Gigabytes