Big O notation

From NoskeWiki
Jump to: navigation, search


Big O notation helps classify the running time and space requirements of algorithms based on how they they respond to input size (n). I learnt big O notation back in first year undergraduate, but occasionally forget the names of different notations, hence I've added the table below to remind me:

Big O notation

Notation Name
O(1) constant
O(log n) logarithmic ... or "linearithmic" for O(n log n)
O(n) linear
O(n2) quadratic
O(nc) * polynomial
O(cn) * exponential
O(n!) * factorial

> * = where c>1