Big-O notation
In Chapter 10 , Sorting and Searching Algorithms, we introduced the concept of big-O notation. What does this mean exactly? It is used to describe the performance or complexity of an algorithm.
When analyzing algorithms, the following classes of functions are the 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 try to execute the increment(1) function, we will have an execution time equal to x. If we...
