Proofs of Algorithm Correctness and Runtime Estimates · Function Growth Rates

Lesson 8

Nikolai Chukhin · Alexander S. Kulikov

Problem. Order the given functions by growth rate (the slowest growing function should be at the top).

This problem can only be submitted at Cogniterra.

  1. \(n\log n\)

  2. \(n^{0.3}\)

  3. \(2^{n}\)

  4. \(\log n\)

  5. \(n^{3}\)

  6. \(\sqrt n\)

  7. \(n^{2}\)