Skip to main content

Big Oh notation and Algorithmic Complexity analysis

Introduction

When executing a particular task using algorithms, one common thing that hits every problem solver brain is the efficient and fast algorithm to solve that problem. But, what do exactly fast and efficient means? Is it the measure of real processing time? No, it's not the measure of real time like second and minutes because the old computer with Pentium processor may take a long time to process the same algorithm than the new Intel i3 processor, or, A bad algorithm written in Assembly may execute faster than a good algorithm written in python. So, run time of program can't be considered to measure algorithmic efficiency. 

Hence, to measure the algorithmic efficiency, the concept of Asymptotic Complexity of a program and a notation for describing this called Big Oh  was introduced. Big Oh is the worst case, Big Omega and Big Theta are best and average case notations. Worst case means we are mostly unlucky for that problem domain , i.e precondition of task do not favour us. Complexity analysis is a tool that allows us to explain how an algorithm behaves as the input grows larger.

Scenarios

Sorting an array of size 10000 compared to array of size 100 and analyzing how run time of the program grows.
Now, Lets dive deeper,
Counting the number of character in a string:

    One simplest approach is traversing through whole string letter by letter and incrementing a counter variable by 1. This algorithmic approach run in linear time with respect to number of character 'n' in the string, i.e, it runs in O(n). 
Why ??
Using this approach the time required to traverse the entire string is proportional to number of character in string, i.e time required to traverse string with 40 character is twice the time required to trverse string with 20 character as the amount of time to look individual character is same.


Another approach is, declaring a variable and storing the number of character in a variable say "length" early in the program, i.e, before storing the very first character. Now, there is no need to look at string, instead one have to check the value of that variable. The accessing of such variable is generally asymptotically constant time operation, or O(1). This is because Asymptotic means "How the run time change as input grows". In this approach the length of string whether it has one character or thousandsof character, the only thing we need to do is to find string length and which can be done by reading the "length" variable and the reading time for this variable is constant regardless of string size. Hence this approach can be referred as running in constant time.
The O(1) does not change with the size of inputs.

Variations

There are many different Big Oh runtimes like O(n), O(n²) etc
O(n²) are asymptotically slower than O(n) i.e if n grows  O(n²) will take more time than O(n). 
This dosen't means O(n) always run faster, maybe if input is smaller then  O(n²) may work faster yet unnoticed
Similarly, we may have logarithmic O(log(n)) for some cases like in Binary search. Binary search cut the array size in half with each operation.
Simpler Program can be anlysed by counting number of nested loop.
  • A single loop over n items has O(n) complexity.
  • A loop within a loop has O(n²) complexity
Different variations of Big Oh
Big Oh Variant

Comments

  1. Nice article Shiva. One question though, is there any measure or mathematics to calculate the complexity in terms of Big Oh notation. Any empirical process at least might be helpful.

    thanks

    ReplyDelete
  2. This comment has been removed by the author.

    ReplyDelete
  3. Good analysis and well elaborated. Good job man :)

    ReplyDelete
  4. It is nice blog Thank you porovide important information and i am searching for same information to save my time Ruby on Rails Online Training Hyderabad

    ReplyDelete

Post a Comment

Popular posts from this blog

Going Through MNIST(Mixed National Institute of Standards and Technology) Datasets in TensorFlow

MNIST Talking About MNIST(Mixed National Institute of Standards and Technology), It is the larger database of the handwritten digit which is used to train and test various Machine learning and Image processing task. [MNIST Wikipedia entry]
As a beginner to Machine learning and equally beginner to TensorFlow, I have decided to go through the first tutorial entitledMNIST For ML Beginners (Mixed National Institute of Standards and Technology)

[In Tensorflow tutorials, make sure to use the your version of mnist_softmax.py by selecting version in branch section, Do not use master branch because the tutorial will be of different tensorflow version ] for tensorflow 0.11 mnist_softmax.py file]

I started my development environment on Pycharm IDE with interpreter location at virtual environment tensorflow which I created previously during Installation of TensorFlow.
 Going through TutorialsThe data hosted on yann.lecun.com is automatically downloaded and read. This is all that tutorials say. from …

All you need to know about Quick Sort Algorithm.

Introduction to Quick Sort Algorithm. A sorting algorithm basically sorts the data structure like array or list in certain order. The order either may be the numerical order or alphabetical order. A Quick-Sort Algorithm is one of the fastest sorting algorithms, which sorts the array based on partitioning the array by choosing an element of the same array as a pivot. All element greater than the pivot are moved to the right direction and all element smaller than the pivot are moved to left.
The basic idea of this algorithm is to select a pivot element in an array and to put the pivot element in its right place and move all smaller entries than pivot of the array to left, and greater entries than pivot to right of the array.  Now the array is divided into two part one part of greater entries than the pivot and another part of the smaller entries than the current pivot element. Now the two-part are recursively applied quicksort to left part and to the right part. Recursion basically ref…