bjc vocab for unit 5

Front

A general description of a task that may be solved algorithmically.

Back

problem

Front

one case of a problem with specific inputs

Back

instance of a problem

Front

Steps proportional to input size; doubling input doubles time.

Back

linear time

Front

Algorithm that checks each list element in order, taking linear time.

Back

linear (sequential) search

Front

Algorithm that starts in the middle of a sorted list, eliminating half until the value is found or all elements are gone.

Back

binary search

Front

Relationship between input size and steps to solve a problem

Back

efficiency

Front

Steps grow slower than input size

Back

sublinear time

Front

Takes the same number of steps regardless of input size.

Back

Constant time.

Front

Steps ∝ input size²

Back

quadratic time

Front

Steps ≤ power of input size (e.g., n^0, n^1, n^2, n^3)

Back

polynomial time