Hi, these is in continuation with 'Analysis of Algorithms 1'. We were talking about algorithm running in n.log n times and n2 times. Yes they are the building blocks of Algorithm analysis. Popularly known notations are:
O(1) constant, O(n) linear, O(n2) quadratic, O(na) polynomial, O(an) exponential, O(log n) algorithmic etc.
This notations are applicable for both space and time. i.e., an algorithm might take away bytes in memory in exponential way, leading the software to crash. or it might happen that the algorithm might spend 'quadratic' time while getting executed.
Please read this paragraph, if you would like to understand further or might skip it. Imagine you have a program which is going to print the square of a value given as an input. We can clearly see that there is no loop required. This can be done in a single step, so what is the complexity? Yes, you'r right its constant O(1). since no loop is required. BTW complexity is what we express in, after an algorithm is analyzed. Now we'll look at one more example, suppose you give an input (positive integer) say 'n', to a program and expect it to print numbers from 1 to n. Now we require to run a loop with temp variable i from 0 to n, and print i. You again guessed it right this is linear complexity O(n).
Note: Constant complexity doesn't mean that there would be only one step, it means 'No Matter What The Value is Given as Input, it is going to take same TIME' or space if that is space complexity.' And the popular example is Hash function in HashSet. For searching a value in HashSet, ideally it is going to take O(1), this doesn't mean it is straight way going to return the value, it has its own calculation to perform. What it actually means is, it is going to take the same time for any input, weather it is 5 or some 500000.
Now we'll discuss about Logarithmic complexity.
Thus the series would look like this: 64, 32, 16, 8, 4, 2, 1. Remembered these values? they are in the reveres order of exponential series.
Ideally our choice move from 'Constant', if not possible we'll think of linear if not quadratic. Thus our choice moves as shown in the following series, first being the best and last being the worst.
O(1), O(log n), O(n), O(n log n), O(n2), O(n3), ..O(an),O(nn).
We'll meet for the further discussion in 'Complexities with examples' post.
O(1) constant, O(n) linear, O(n2) quadratic, O(na) polynomial, O(an) exponential, O(log n) algorithmic etc.
This notations are applicable for both space and time. i.e., an algorithm might take away bytes in memory in exponential way, leading the software to crash. or it might happen that the algorithm might spend 'quadratic' time while getting executed.
Please read this paragraph, if you would like to understand further or might skip it. Imagine you have a program which is going to print the square of a value given as an input. We can clearly see that there is no loop required. This can be done in a single step, so what is the complexity? Yes, you'r right its constant O(1). since no loop is required. BTW complexity is what we express in, after an algorithm is analyzed. Now we'll look at one more example, suppose you give an input (positive integer) say 'n', to a program and expect it to print numbers from 1 to n. Now we require to run a loop with temp variable i from 0 to n, and print i. You again guessed it right this is linear complexity O(n).
Note: Constant complexity doesn't mean that there would be only one step, it means 'No Matter What The Value is Given as Input, it is going to take same TIME' or space if that is space complexity.' And the popular example is Hash function in HashSet. For searching a value in HashSet, ideally it is going to take O(1), this doesn't mean it is straight way going to return the value, it has its own calculation to perform. What it actually means is, it is going to take the same time for any input, weather it is 5 or some 500000.
Now we'll discuss about Logarithmic complexity.
Before going formally, I would like to deal this with a funny example. Did you remember PAPER DANCE? Here a sweet couple is asked to dance on a sheet of paper, shortly the paper size is folded to half the size and are again asked to dance, this is repeated 3 or 4 times, but shortly the poor boy has to hold her in his arms, God save him :). This has happened since the paper started shrinking logarithmic. Yes, it shows an opposite effect to what we saw in case of exponential series.
Thus the series would look like this: 64, 32, 16, 8, 4, 2, 1. Remembered these values? they are in the reveres order of exponential series.
Ideally our choice move from 'Constant', if not possible we'll think of linear if not quadratic. Thus our choice moves as shown in the following series, first being the best and last being the worst.
O(1), O(log n), O(n), O(n log n), O(n2), O(n3), ..O(an),O(nn).
We'll meet for the further discussion in 'Complexities with examples' post.
Nice explanation! thanks a ton.
ReplyDelete