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 Big O notation characterizes functions according to their growth rates: different functions with the same growth rate may be represented using the same O notation. The letter O is used because the growth rate of a function is also referred to as the order of the function. A description of a function in terms of big O notation usually only provides an upper bound (read: worst case) on the growth rate of the function.
You will find questions about Big O notation during technical design (or interview). As my mathematics level is just "good-enough-to-pass", sometimes I also have difficulties to answer such questions. In this post, I tried to combined some sources (from internet of course) for my own understanding but I also believes that it can help others who struggle with same questions.
Below are some common O notation (orders of growth) along with descriptions and examples:
O(1) - Constant
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 isFirstElementNull(List<String> elements) {
return elements.get(0) == null;
}
O(n) - Linear
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 containsValue(List<String> elements, String value) {
for (String element : elements) {
if (element.equals(value)) {
return true;
}
}
return false;
}
O(n2) - Quadratic
O(n2) 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) - Cubic, O(n4), etc... The worst case assumed that the duplicates is found in the last index of both outer and inner:
boolean containsDuplicates(List<String> elements) {
for (int outer = 0; outer < elements.size(); outer++) {
for (int inner = 0; inner < elements.size(); inner++) {
// Don't compare with self
if (outer == inner) {
continue;
}
if (elements.get(outer).equals(elements.get(inner))) {
return true;
}
}
}
return false;
}
O(2n) - Exponential
O(2n) denotes an algorithm whose growth doubles with each addition to the input data set. The growth curve of an O(2n) function is exponential - starting off very shallow, then rising meteorically. An example of an O(2n) function is the recursive calculation of Fibonacci numbers:
int fibonacci(int number) {
if (number <= 1) {
return number;
}
return fibonacci(number - 2) + fibonacci(number - 1);
}
O(log n) - Logarithmic
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.
// Java implementation of recursive Binary Search
class BinarySearch {
// Returns index of x if it is present in arr[l..r], else return -1
int binarySearch(int arr[], int l, int r, int x) {
if (r >= l) {
int mid = l + (r - l) / 2;
// If the element is present at the middle itself
if (arr[mid] == x) {
return mid;
}
// If element is smaller than mid, then
// it can only be present in left subarray
if (arr[mid] > x) {
return binarySearch(arr, l, mid - 1, x);
}
// Else the element can only be present
// in right subarray
return binarySearch(arr, mid + 1, r, x);
}
// We reach here when element is not present in array
return -1;
}
// Driver method to test above
public static void main(String args[]) {
BinarySearch ob = new BinarySearch();
int arr[] = {2, 3, 4, 10, 40};
int n = arr.length;
int x = 10;
int result = ob.binarySearch(arr, 0, n - 1, x);
if (result == -1) {
System.out.println("Element not present");
} else {
System.out.println("Element found at index " + result);
}
}
}
/* This code is contributed by Rajat Mishra */
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.
The most common attributes of logarithmic running-time function are that:
- the choice of the next element on which to perform some action is one of several possibilities, and
- only one will need to be chosen.
or
- the elements on which the action is performed are digits of n
This is why, for example, looking up people in a phone book is O(log n). You don't need to check every person in the phone book to find the right one; instead, you can simply divide-and-conquer by looking based on where their name is alphabetically, and in every section you only need to explore a subset of each section before you eventually find someone's phone number.
Of course, a bigger phone book will still take you a longer time, but it won't grow as quickly as the proportional increase in the additional size.
Real-Life Scenario for Big O Notation
We can expand the phone book example to compare other kinds of operations and their running time. We will assume our phone book has businesses (the "Yellow Pages") which have unique names and people (the "White Pages") which may not have unique names. A phone number is assigned to at most one person or business. We will also assume that it takes constant time to flip to a specific page.
Here are the running times of some operations we might perform on the phone book, from best to worst:
- O(1) (best case): Given the page that a business's name is on and the business name, find the phone number.
- O(1) (average case): Given the page that a person's name is on and their name, find the phone number.
- O(log n): Given a person's name, find the phone number by picking a random point about halfway through the part of the book you haven't searched yet, then checking to see whether the person's name is at that point. Then repeat the process about halfway through the part of the book where the person's name lies. (This is a binary search for a person's name.)
- O(n): Find all people whose phone numbers contain the digit "5".
- O(n): Given a phone number, find the person or business with that number.
- O(n log n): There was a mix-up at the printer's office, and our phone book had all its pages inserted in a random order. Fix the ordering so that it's correct by looking at the first name on each page and then putting that page in the appropriate spot in a new, empty phone book.
For the below examples, we're now at the printer's office. Phone books are waiting to be mailed to each resident or business, and there's a sticker on each phone book identifying where it should be mailed to. Every person or business gets one phone book.
- O(n log n): We want to personalize the phone book, so we're going to find each person or business's name in their designated copy, then circle their name in the book and write a short thank-you note for their patronage.
- O(n2): A mistake occurred at the office, and every entry in each of the phone books has an extra "0" at the end of the phone number. Take some white-out and remove each zero.
- O(n ยท n!): We're ready to load the phone books onto the shipping dock. Unfortunately, the robot that was supposed to load the books has gone haywire: it's putting the books onto the truck in a random order! Even worse, it loads all the books onto the truck, then checks to see if they're in the right order, and if not, it unloads them and starts over. (This is the dreaded bogo sort.)
- O(nn): You fix the robot so that it's loading things correctly. The next day, one of your co-workers plays a prank on you and wires the loading dock robot to the automated printing systems. Every time the robot goes to load an original book, the factory printer makes a duplicate run of all the phonebooks! Fortunately, the robot's bug-detection systems are sophisticated enough that the robot doesn't try printing even more copies when it encounters a duplicate book for loading, but it still has to load every original and duplicate book that's been printed.
Sources:
At the end of the day, the moral of story is:
- Bigger problems to solve means efficiency is more important
- Bigger problems to solve, you need faster computer (CPU)
Desson AriawanProgrammer
