Week 3

Question 1

measures the worst-case complexity of an algorithm. n represents the number of inputs.

Answer 1

The Big-O notation

Question 2

does not change with respect to input space. Hence, it is referred to as being —. An example of an it algorithm is accessing an item in the array by its index.

Answer 2

O(1) - Constant Time

Question 3

applies to algorithms that must do n operations in the worst-case scenario.

Answer 3

O(n) - Linear Time

Question 4

The runtime grows logarithmically as the input size increases. Typically seen in algorithms that divide the problem in half each time.

Answer 4

O(log n) - Logarithmic Time

Question 5

The runtime grows proportionally to the square of the input size. Often seen in algorithms with nested loops.

Answer 5

O(n^2) - Quadratic Time

Question 6

The runtime grows proportionally to the cube of the input size. Less common but seen in some complex algorithms with multiple nested loops.

Answer 6

O(n^3) - Cubic Time

Question 7

The runtime grows faster than exponential time. This is extremely inefficient and rare.

Answer 7

O(n^n) - Exponential Time (Super-Exponential)