ewshiawuglawehsar

problem

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

instance 

One case of a problem with specific inputs

decision problem

A type of problem with a true/false answer

optimization problem

A problem with the goal of finding the best solution among many

sequential computing

A computational model in which operations are performed in order one at a time

parallel computing

A computational model in which the problem is broken into smaller steps, some of which are performed at the same time

distributed computing

A form of parallel computing that uses multiple computers, perhaps even spread out around the world

processor

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

speedup

How many times as fast the parallel solution is compared to the sequential solution

simulation

Computer representations of real things or situations that vary over time

linear time 

How long an algorithm takes if the number of steps is proportional to the input size

linear search 

An algorithm that searches a list by checking each element of a list in order, also called a sequential search

binary search 

An algorithm that starts a search 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

efficiency

The relationship between the input size and the number of steps required to solve a problem

sublinear time 

How long an algorithm takes if the number of steps grows more slowly than the size of the input

constant time 

How long an algorithm takes if it takes the same number of steps regardless of input size

quadratic time 

How long an algorithm takes if the number of steps is proportional to the square of the input size

polynomial time 

How long an algorithm takes if the number of steps is less than or equal to a power of the size of the input

exponential time 

How long an algorithm takes if the number of steps is proportional to an exponential function of the size of the input, such as 2ⁿ, 10ⁿ, etc.