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).

5 points

  1. \(n\log n\)

  2. \(n^{0.3}\)

  3. \(2^{n}\)

  4. \(\log n\)

  5. \(n^{3}\)

  6. \(\sqrt n\)

  7. \(n^{2}\)