Big O notation is a special way to describe the speed of algorithms.
Let's say we need to find a name in the phone book (yes, that old book with phone numbers). We can, of course, search all the names one by one, but this will be time consuming, better at this point to open the phone book halfway and see if we hit it. If not we open the phone book in the middle again, this time between the previous middle and the beginning or end of the book, and so on until we find the right name.
To see which algorithm is faster we can measure the time between the two algorithms simply by measuring the time in which they executed. But what if we are looking for the first name in the phone book - the first way will prove to be more efficient as it will only need one operation to complete. But what if we are looking for the last name in the phone book - then the second algorithm will turn out to be incredibly faster.
Which algorithm to choose, then? With help comes the Big O notation
The big O notation specifies the worst-case running time of the algorithm
The information alone on how long an algorithm took to execute is not sufficient, more important information for the programmer is how much the execution time increases as the number of elements increases.
Big O notation looks like this:
O(n) - First comes big O, and in parentheses the number of operations to be performed in the worst possible case
The name "Big O notation" comes from the fact that it puts the letter O in front of the number of operations (yes, seriously!)
Below is a list of the most common execution times expressed in the Big O notation:
O(log n) - logarithmic time, e.g binary search
O(n) - linear time, e.g linear search
O(n ⋅ log n) - e.g quicksort
O(n2) - e.g selection sort
O(n!) - very slow algorithm, e.g traveling salesmen problem
Summary
the speed of execution of algorithms is not expressed in seconds, but in the rate of increase in the number of operations
When discussing the speed of the algorithm, it is stated how fast the execution time increases as the size of the input set increases
The execution time of the algorithms is expressed in the Big O notation
The larger the dataset the greater the difference in algorithm execution time
Top comments (0)