Big-O notation

Big-O notation compactly describes the running time of an algorithm. An algorithm’s efficiency in terms of its worst-case running time, which is the largest amount of time an algorithm can take given the most difficult input of a fixed size

For example, if your algorithm for sorting an array of n numbers takes roughly n2 operations for the most difficult dataset, we say that the running time of your algorithm is O(n2).

In reality, any number of operations, such as 1.5n2, n2 + n + 2, or 0.5n2 + 1; all these algorithms are O(n2) because big-O notation only cares about the term that grows the fastest with respect to the size of the input.

A function f(n) is Big-O of function g(n), or O(g(n)), when f(n) ≤ c · g(n) for some constant c and sufficiently large n.

Big O notation is 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.

O(1) – describes an algorithm that will always execute in the same time (or space) regardless of the size of the input data set.

def CheckAge(age):
    if (age<18):
       return False
return True

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 favours the worst-case performance scenario; a mistake could be greater t than no of mismatch 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.

def FindMistake(dna, pattern, kmer, noofmismatch):
    mistake = 0
    for i in range(0, kmer, 1):
        if (dna[i]!= pattern[i]):
           mistake+=1
           if (mistake>noofmismatch):
              return False
    return True

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), O(N4) etc.

def ContainsDuplicates(strings):
    for i in xrange(len(strings):
        for j in xrange(len(strings):
            if (i == j): #Don't compare with self
               continue;
            if (strings[i] == strings[j]):
               return True
    return False;

O(2N) – denotes an algorithm whose growth will double with each additional element in the input data set. The execution time of an O(2N) function will quickly become very large.

Logarithms – O(log N) is log base 2

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.

The graph below compares the running times of various algorithms.

Linear – O(n), Quadratic – O(n2), Cubic – O(n3), Logarithmic – O(log n), Exponential – O(2n), Square root – O(sqrt n)

bigo

The best sorting algorithms (such as mergesort) run in O(n log n) time.  Slower ones (such as bubble sort, selection sort, and insertion sort), take O(n2) time.

½n² – O(n²).
8(sqrt(n)) – O(sqrt(n))
log n – O(log n)
Bi² – O(1), doesn’t grow with n.

Let’s take this expression 2n² + 6n + 20 log n.
Which of these is it Big Theta of?
yes -> 2n² + 6n + 20 log n – itself?
no -> 20 log n – with the largest coefficient?
yes -> 20 n² – the highest order(n²),but with the largest coefficient (20).
yes -> n² – n² by itself?
no -> n² log n – a combination of n² and log n together

Explanation, 2n² + 6n + 20 log n, you need to take the one with the fastest growth rate.

Log n is piddly as n gets big compared to n,
n is actually pretty piddly as n gets big compared to n².
N² is really the only thing that matters here.
2 – This constant(coefficient) in front of the n² is not going to matter in Big Theta world, because we can go above it or below it.
Any coefficient in here gives you the same answer.

n² log n
The main thing is rate of growth, n^2 gives incredible rate of growth compared to other expressions
for example n= 1.000.000=>20n=20.000.000, while n^2=1.000.000*1.000.000,
as you see, 20n is quite nothing compare to n^2
This is not. Once you multiply another term in here, even though it grows really slowly,
It’s not a constant. It changes the asymptotic growth rate.

2_7_bigtheta_set

Advertisement

One response to “Big-O notation

  1. Vednath Mishra September 10, 2017 at 11:22 am

    This was just so amazing. I found it really helpful to understand the Big O notation concepts as in our reference books, its really difficult to understand. I also found some good explanation here as well: http://www.codingalpha.com/big-o-notation/

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: