Big-O Notation

Flashcards on Big-O notation, covering growth rates, examples, and loop complexities.

What is the purpose of Big-O notation?

To describe the growth rate of functions, usually establishing an upper boundary for the growth of a function T(n) for large n.

What is constant growth in Big-O notation?

O(1)

What is logarithmic growth in Big-O notation?

O(log n)

What is linear growth in Big-O notation?

O(n)

What is quadratic growth in Big-O notation?

O(n^2)

What is a polynomial growth in Big-O notation?

O(n^c) where c is a constant number

What is exponential growth in Big-O notation?

O(c^n) where c is a constant number

What is factorial growth in Big-O notation?

O(n!)

In Big-O notation, if T(n) is O(n^2), is it also O(n^3)?

Yes, because n^3 grows faster than n^2.

When determining Big-O complexity, what should you find?

The dominant term(s).

What is the time complexity of a single loop with O(1) instruction running constant times?

O(1)

What is the time complexity of a single loop incrementing/decrementing by constant c with O(1) instruction?

O(n)

What is the time complexity of a single loop dividing/multiplying by constant c with O(1) instruction?

O(log n)

What is the time complexity of nested loops?

Complexity of inner loop*complexity of outer loop