Big O notation

In Chapter 13, Sorting and Searching Algorithms, we introduced the concept of big O notation. What does it mean, exactly? It is used to describe the performance or complexity of an algorithm. Big O notation is used to classify algorithms according to how much time it will take for the algorithm to run, depending on space/memory requirements as the input size grows.

When analyzing algorithms, the following classes of function are most commonly encountered:

Notation	Name
O(1)	Constant
O(log(n))	Logarithmic
O((log(n))c)	Poly-logarithmic
O(n)	Linear
O(n2)	Quadratic
O(nc)	Polynomial
O(cn)	Exponential

Understanding big O notation

How do we measure the efficiency of an algorithm? We usually use resources such as CPU (time) usage, memory usage, disk usage, and network usage. When talking about big O notation, we usually consider CPU (time) usage.

Let's try to understand how big O notation works using some examples.

O(1)

Consider the following function:

function increment(num){ 
  return ++num; 
} 

If we...