Tuesday, May 14, 2013

What do you understand by Big O Notation, Why is it important in software development ?

What do you understand by Big O Notation?

Big O Notation is a mechanism used to measure the relative inefficiencies of Algorithms in terms of space and time. It makes us understand how execution time & memory requirements of an algorithm grow as a function of increasing input size. In this notation, O stands for the Order of magnitude.

Constant O(1)
A program whose running time’s order of growth is constant, executes a fixed number of operations to finish the job, thus its running time does not depend on N.

Linear O(N)
Program that spends a constant amount of time processing each piece of input data and thus running time is proportional to the N.

Following are the examples of Big O, in increasing order of their magnitude.
# Big O Notation Name Example
1. O (1) Constant-time Searching from a HashMap, check a number for even/odd
2. O (log n) Logarithmic Find an item inside sorted array using Binary Search
3. O (n) Linear Printing all elements from an array
4. O (n log n) LogLinear Sorting using Merge Sort
5. O (n2) Quadratic Bubble Sorting Algorithm
6. O (2n) Exponential Shortest Path Problem Djigstraw Algorithm
7. O (n!) Factorial Solving Travelling Sales Man Problem

Importance of Big O

We should always keep time efficiencies in mind while designing an algorithm using existing data structures, otherwise there could be sever performance penalties for using wrong data structure for a given scenario.

Base of Logarithm is irrelevant in Big O Notation

The base of algorithm is not relevant with respect to the order of growth, since all logarithms with a constant base are all related by a constant proportion, so log N is used when referring to the order of growth. But also note that base in case of exponent matters, because it makes lot of difference.

Time efficiency in Big O notation for few Java Collections

ArrayList (ignoring the time taken by array resize operation)
O(1) for add, size and get
O(n) for toString() method

O(1) for peek, element and size
O(log n) for offer, poll, remove() and add
O(n) for remove(Object) & contains(Object)

HashMap (with no collisions)
O(1) for get operation
O(1) for put operation

O(1) for removal
O(1) for add & poll method
O(n) for toString() method


No comments:

Post a Comment

Your comment will be published after review from moderator