The complexity relates to how many steps your algorithm must take (approximately) to work with some data.
represents how many elements are contained in the data.
is used to show the correlation between amount of data and the steps the algorithm takes.
Let's say we have an array named arr
of length n
What's the complexity of an algorithm which prints a random element from arr
The complexity is O(1) because there's a
fixed number of steps involved, which don't depend on n
(even if the number of steps isn't actually one).
What's the complexity of an algorithm which prints all the elements from arr
The complexity is O(n) because there's n steps involved. The number of steps depends on n.
What's the complexity of an algorithm which prints all elements from arr
It is O(3n) but we say it's O(n), because we may disregard coefficients such as 3 because they don't depend on n.
What's the complexity of an algorithm searching for an element in arr
That is: we are given an element and we must return its position in arr
The complexity is O(n) because in the worst case we won't even find the element, and we will search all n
elements of arr
But what is the complexity of a binary search on array arr
, after the array was sorted?
(Binary search requires the array to be sorted.)
The complexity is O(log2
n) usually written simply as O(log n).
This is because our binary search algorithm always cuts the array in half, so there's half less data to search the element in.
arr = [1 1 3 4 5 5 6] search for 6
compare to middle element: 4 < 6 (take right half)
arr = [5 5 6] search for 6
compare to middle element: 5 < 6 (take right half)
arr =  search for 6, found
Of course the above is a simplification of the actual algorithm but that's close to how it works.
What about an algorithm that creates a square matrix named mat
out of array arr
It copies the n
elements of array arr
into matrix mat
a number of n
Considering that a single element copied is a step, we have a number of n2
So the complexity of the algorithm is O(n2
Read more here: