The complexity relates to how many steps your algorithm must take (approximately) to work with some data.
The
n represents how many elements are contained in the data.
The
n 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
finite 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 three times?
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(log
_{2}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 = [6] search for 6, found |
Of course the above is a simplification of the actual algorithm but that's close to how it works.
http://en.wikipedia.org/wiki/Binary_search
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 times.
Considering that a single element copied is a step, we have a number of n
^{2} steps.
So the complexity of the algorithm is O(n
^{2}).
Read more here:
http://en.wikipedia.org/wiki/Time_complexity#Table_of_common_time_complexities