Simplified Big-O
Simplified Big O Notation
Algorithm
An Algorithm is a method or step by step procedure to solve a specific task. It is important that the quality of such an Algorithm be measured before applying it in bulk scale. This is known as performance of an Algorithm.
Internal Factors
Time required to run the algorithm
Space required
External Factors
Size of input data
Speed of the computer
Quality of Compiler
Computational complexity is the study of factors to determine how much resource is necessary to run the algorithm efficiently, which mostly covers the Internal Factors –
Time (Temporal Complexity)
Space (Space Complexity)
Big O Notation
Big O notation is used in Computer Science to describe the performance or complexity of an algorithm. Big O specifically describes the worst-case scenario, and can be used to describe the execution time required or the space used (e.g. in memory or on disk) by an algorithm.
As a programmer first and a mathematician second (or maybe third or fourth) I found the best way to understand Big O thoroughly was to produce some examples in code. So, below are some common orders of growth along with descriptions and examples where possible.
O(1)
O(1) describes an algorithm that will always execute in the same time (or space) regardless of the size of the input data set.
boolean function_check (String str[ ])
{
if(str[0] == null)
{
return true;
}
return false;
}
O(N)
O(N) describes an algorithm whose performance will grow linearly and in direct proportion to the size of the input data set. The example below also demonstrates how Big O favors the worst-case performance scenario; a matching string could be found during any iteration of the for loop and the function would return early, but Big O notation will always assume the upper limit where the algorithm will perform the maximum number of iterations.
boolean function_check(String str[], String value)
{
for (int i = 0; i < str.length; i++)
{
if(str [i] = = value)
{
return true;
}
}
return false;
}
O(N²)
O(N²) represents an algorithm whose performance is directly proportional to the square of the size of the input data set. This is common with algorithms that involve nested iterations over the data set. Deeper nested iterations will result in O(N3), O(N4) etc.
boolean function_check_duplicate(String str[])
{
for(int i = 0; i < str.length; i++)
{
for(int j = 0; j < str.length; j++)
{
if(i == j) // Don’t compare with self
{
continue;
}
if(str[i] == str[j])
{
return true;
}
}
}
return false;
}
O(2^{N})
O(2^{N}) denotes an algorithm whose growth will double with each additional element in the input data set. The execution time of an O(2^{N}) function will quickly become very large.
Logarithms
Logarithms are slightly trickier to explain so I’ll use a common example:
Binary search is a technique used to search sorted data sets. It works by selecting the middle element of the data set, essentially the median, and compares it against a target value. If the values match it will return success. If the target value is higher than the value of the probe element it will take the upper half of the data set and perform the same operation against it. Likewise, if the target value is lower than the value of the probe element it will perform the operation against the lower half. It will continue to halve the data set with each iteration until the value has been found or until it can no longer split the data set.
This type of algorithm is described as O(log N). The iterative halving of data sets described in the binary search example produces a growth curve that peaks at the beginning and slowly flattens out as the size of the data sets increase e.g. an input data set containing 10 items takes one second to complete, a data set containing 100 items takes two seconds, and a data set containing 1000 items will take three seconds. Doubling the size of the input data set has little effect on its growth as after a single iteration of the algorithm the data set will be halved and therefore on a par with an input data set half the size. This makes algorithms like binary search extremely efficient when dealing with large data sets.
Big–O Complexity for a Few Algorithms
Sl. | Type | Example | Meaning | Complexity |
1. | One arithmetic operation, one assignment, one read, one write | if (a>b)…int a = 10,s = y.readLine(),
System.out.println(s); |
Means that no matter how large the input is, the time taken doesn’t change. | O(1) |
2. | Searching in an unsorted array (Linear Search) | – | O(n) | |
3. | Searching in a sorted array (Binary Search) | – | Any algorithm which cuts the problem in half each time | O(log n) |
4. | Single loops | – | means that for every element, you are doing a constant number of operations, such as comparing each element to a known value | O(n) |
5. | Nested Loop | Quadratic | Means that for every element, you do something with every other element, such as comparing them. | O(n^{2}) |
6. | Selection Sort | – | O(n^{2}) | |
7. | Insertion Sort | – | O(n^{2}) | |
8. | Triple nested loops | Cubic | O(n^{3}) | |
9. | Exponential | – | Means that the time taken will double with each additional element in the input data set. | O(2^{n}) |
10. | Merge Sort | – | Means that you’re performing an O(log n) operation for each item in your input. Most (efficient) sort algorithms are an example of this. | O(n log n) |
11. | Quick Sort | – | O(n log n) | |
12. | All possible permutations | – | Means this involves doing something for all possible permutations of the n elements. | O(n!) |