Embedded Files
4.2.8 Deduce the efficiency of an algorithm in the context of its use.
4.2.8 Deduce the efficiency of an algorithm in the context of its use.
Big O notation
Big O notation
"Big O notation (with a capital letter O, not a zero), also called Landau's symbol, is a symbolism used in complexity theory, computer science, and mathematics to describe the asymptotic behavior of functions.
Basically, it tells you how fast a function grows or declines. Landau's symbol comes from the name of the German number theoretician Edmund Landau who invented the notation. "
The letter O is used because the rate of growth of a function is also called its order.
Big O notation characterises functions according to their growth rates: different functions with the same growth rate may be represented using the same O notation.
Big O notation is used to classify algorithms according to how their running time or space requirements grow as the input size grows
Big O notation is useful when analysing algorithms for efficiency.
How does it work?
How does it work?
For example, when analyzing some algorithm, one might find that the time (or the number of steps) it takes to complete a problem of size n is given by
If we ignore constants (which makes sense because those depend on the particular hardware the program is run on) and slower growing terms, we could say
Examples
Examples
Content directly taken off of <https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/>
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.
public int getFirstWord(String[] someSet) {
return someSet[0];
}
O(N)
O(N)
describes an algorithm whose performance will grow linearly and in direct proportion to the size of the input data set.
public int searchWord(String[] someSet, String toSearch) {
int index = 0;
for (int i = 0; i < someSet.length; i++) {
if (toSearch.equals(someSet[i])) {
index = i;
break;
}
}
return index;
}
O(N2) power of 2
O(N2) power of 2
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.
public boolean isThereDuplicates(String[] someSet) {
for (int i = 0; i < someSet.length; i++) {
for (int j = 0; j < someSet.length; j++) {
if (i == j) {
continue;
}
if (someSet[i].equals(someSet[j])) {
return true;
}
}
}
return false;
}
O(2N)
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:
public int someFunction(int n) {
if (n <= 1) {
n = 1;
} else {
n = someFunction(n - 2) + someFunction(n - 1);
}
return n;
}
O(log N)
O(log N)
Logarithmic - The type of algorithm described as O(log N) can be best described with Binary Search algorithm. 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.
public int someSearch(int arr[], int x) {
int l = 0, r = arr.length - 1;
while (l <= r) {
int m = l + (r - l) / 2;
// Check if x is present at mid
if (arr[m] == x) {
return m;
}
// If x greater, ignore left half
if (arr[m] < x) {
l = m + 1;
}
// If x is smaller, ignore right half
else {
r = m - 1;
}
}
// if we reach here, then element was not present
return -1;
}
Page updated
Report abuse