Growth orders

Exercises 1.8 and 1.9

Sort the following functions in increasing order of asymptotic growth. If two functions have the same asymptotic growth, point it out.

The figure above is meant to be a visual reminder of the growth rate of functions. It is morally correct but it contains some small errors. Can you spot them? If not, look at the theory-bit asymptotics.

5n \ln n

4n\sqrt{n}

\log_\pi (n^n )

\frac{n}{\log_2 n}

\frac{n}{\ln n}

3 \ln(7^n)

You might want to refresh how to compute limits and properties of the logarithms.

Classify the functions below in such a way that f(n) and g(n) belong to the same class if and only if f(n) = \Theta(g(n)), and enumerate the classes according to their growth order:

The figure above is meant to be a visual reminder of the growth rate of functions. It is morally correct but it contains some small errors. Can you spot them? If not, look at the theory-bit asymptotics.

n

\sqrt{n}

n^{1.5}

n^2

n \log n

n \log \log n

(\log \log n)^2

n \log^2 n

\frac{n^3}{n-1}

n^{\log n}

n\log(n^2)

21n

2^n

2^{\sqrt{n}}

2^{\sqrt{\log n}}

2^{n/2}

37

2^{2^n}

\frac{2}{n}

n^2\log n

You might want to refresh how to compute limits and properties of the logarithms.

Extra

What about n! and 3^n? How do they compare with the rest?

Once you solved the exercises above you might want to double check the correctness of your answers using a Compuer Algebra System.

You could use the box below to perform symbolic calculations in SageMath and use them to double-check the correctness of your calculations. If you click on the “Evaluate” button this will tell you something on the respective asymptotic growth of the functions \log(x) and \sqrt{x}. Which one grows faster?

Use the box above with different functions for f and g. A minimal explanantion of the syntax is here.

Important

Do not use n as the name of your variable, since this would tell SageMath to treat it as an integer. In our context, this would only create problems. Use x instead.