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

Post a Comment

Popular posts from this blog

Getting Started With Tensorflow

TensorFlow Introduction It is an open source library for machine learning. It was developed at Google by Google brain team. For more info regarding Tensorflow check the Wikipedia entry . Getting Started with Installation Referring to GitHub  link  and choosing the virtual environment Installation Procedure. Following this link  here  for installation procedure of Tensorflow library  CPU version. We can choose any version listed along with CPU/GPU version. After activating the python virtual environment as listed on installation manual console of our environment will be changed like this as in the picture below. Console window changed with (tensorflow) at beginning.  After this steps below, export TF_BINARY_URL=https://storage.googleapis.com/tensorflow/linux/cpu/tensorflow-0.11.0-cp27-none-linux_x86_64.whl pip install --upgrade $TF_BINARY_URL Faced a problem during installation with this message in console. tensorflow-0.11.0-cp27-none-linux_x86_64.whl is no

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 entitled   MNIST 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 Tutorials The data hosted on yann.lecun.com  is automatically downloaded and read. This is all