Algorithms

Question 1

What does it mean when a function has constant growth?

Answer 1

A function has “constant” growth if its output does not change based on the input, the nn. The easy way to identify constant functions is find those that have no nn in their expression anywhere, or have n^0n
0. In this case, 11 and 10001000 are constant.

Question 2

What does it mean when a function has a linear growth?

Answer 2

A function has “linear” growth if its output increases linearly with the size of its input. The way to identify linear functions is find those where nn is never raised to a power (although n^1 n
1 is OK) or used as a power. In this case, 3n and (3/2)n are linear.

Question 3

What does it mean when a function has polynomial growth?

Answer 3

A function has “polynomial” growth if its output increases according to a polynomial expression. The way to identify polynomial functions is to find those where n is raised to some constant power. In this case, 2n^3, 2n
3 and 3n^2 are polynomial.