AP CSP UNIT 5 CONTENT REVIEW

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

• problem
• instance of a problem

one case of a problem, with specific inputs

• instance of a problem
• problem

the number of steps is proportional to the input size; doubling the input size doubles the time required

• linear time
• exponential time

• quadratic time

an algorithm that checks each element of a list in order, a process which takes linear time

• linear search
• binary search

an algorithm that 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

• binary search
• linear search

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

• efficiency
• sublinear time

• quadratic time

• exponential

the number of steps grows more slowly than the input size

• sublinear time
• quadratic time

• linear time

• exponential time

takes the same number of steps regardless of input size

• constant time
• quadratic time

• sublinear time

• exponential time

the number of steps is proportional to the square of the input size

• quadratic time
• sublinear time

• exponential time

• constant

the number of steps is less than or equal to a power of the size of the input, such as constant (n^0), sublinear, linear (n^1), quadratic (n^2), or cubic (n^3)

• polynomial time
• exponential time