A problem is a general description of a task that may (or may not) be solved algorithmically.

An instance of a problem is one case of a problem, with specific inputs.

An algorithm takes linear time if multiplying the input size by ten multiplies the time required by ten.

A linear search (or sequential search) algorithm checks each element of a list in order, a process which takes linear time.

A binary search algorithm starts in the middle of a sorted list and repeatedly eliminates half the list until either the desired value is found or all elements have been eliminated.

Linear search does a complete traversal of the list. Binary search saves time by doing a partial traversal of the list.

The relationship between the input size and the number of steps required to solve a problem is the efficiency of the algorithm used to solve the problem.

An algorithm takes linear time the number of steps is proportional to the input size; doubling the input size doubles the time required.

An algorithm takes sublinear time if the time grows more slowly than the size.

An algorithm takes constant time if it takes the same amount of time regardless of input size.

An algorithm takes quadratic time if the number of steps is proportional to the square of the input size.

An algorithm takes polynomial time if the number of steps is less than or equal to a power of the size of the input, such as constant (n⁰ ), sublinear, linear (n¹), quadratic (n²), or cubic (n³).

An algorithm takes exponential time if the number of steps is less than or equal to a function like 2ⁿ , 10ⁿ , etc., which is much slower than any polynomial.

The term "reasonable time" describes any algorithm that runs in polynomial time. Exponential time algorithms are not considered reasonable.

A decision problem is a problem with a true/false answer (for example, "is 5,825,496,221 a prime number?")

An optimization problem is one with the goal of finding the best solution among many (for example, "what's the best school schedule to place every student into as many of their requested classes as possible?")

A decidable problem a decision problem for which it's possible to write an algorithm that will give a correct output for all inputs.

An undecidable problem is the opposite. It's not possible to write an algorithm that will give a correct output for all inputs—even though it might be possible for some of them.

In sequential computing, operations are performed in order one at a time.

In parallel computing, the program is broken into smaller steps, some of which are performed at the same time. Modern computers have multiple processors (2, 4, or 8) in a single computer, so you can do small-scale parallel processing on the machine on your desk.

Distributed computing is a form of parallel computing that uses multiple computers (perhaps even spread out around the world).

A processor is a piece of circuitry inside a computer that processes the instructions from computer programs.

Programmers refer to the speedup of parallel solution to describe how many times as fast the parallel solution is compared to the sequential solution: