Algorithms- Getting started

To learn the analysis of algorithms and to dive in the study of complexity for algorithms few mathematical concepts are required and used in almost all cases.
I am presenting few concepts in simple manner, so a beginner  can grasp it easily and use it in further study of algorithms.
Asymptotic notations:

Asymptotic notations

Big O notation  (middle image in above figure):
O(g(n)) = {f(n): there exist positive constants c and n0 such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0}.
It specifies that function gives a upper bound on the complexity of the algorithm and it's the highest value that an algorithm could achieve and not depends on any particular condition, whatever is the input its the highest bound on the time.
whenever we write f(n) = O(g(n)) then f(n) is upper bounded by g(n), it means g(n) is having more value than f(n) or in other words{though not technically correct, we can write value of f(n)<= g(n)}.

Θ-notation :(First image in above fig.)
Θ(g(n)) = {f(n) : there exist positive constants c1, c2, and n0 such that 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) for all n ≥ n0}.
function f(n) is sandwiched between g(n) for any two arbitrary constants c1 and c2 such that for any value(eg c1=1/2) f(n) is smaller than g(n) as well as for any other value (eg c2=3/2) f(n) is greater than g(n).
Θ notation is more stronger than O notation and we can write Θ subset of O.
The definition of Θ(g(n)) requires that every member f(n) Θ(g(n)) be asymptotically non-negative, that is, that f(n) be non-negative whenever n is sufficiently large. (An asymptotically positive function is one that is positive for all sufficiently large n.) Basically it is all related to set theory and we denote each set as a set of functions and complexity is based only for positive functions only.

Ω-notation: (Last image in above fig.) :
Ω(g(n)) = {f(n): there exist positive constants c and n0 such that 0 ≤ cg(n) ≤ f(n) for all n ≥ no}.
it means function f(n) is greater than g(n) for a sufficient value of constant c.

Few facts:

• The constants(c1,c2 etc)  mentioned in each case should be only numerical constants and should not be any exponential or any other value , for example :

2ⁿ⁺¹== O(2ⁿ) but  2²ⁿ != O(2ⁿ) because  we can write 2ⁿ⁺¹  as 2*2ⁿ and consider 2 as constant(c1) but in case of  2²ⁿ  ,it can be written as 2ⁿ *2ⁿ and here 2ⁿ cannot be considered as a constant. So it can’t be considered as O(2ⁿ).

• f(n) = Θ(g(n)) iff f(n) = O(g(n)) and f(n) = Ω(g(n))  because in that way only it will be upper bounded by g(n) as well as lower bounded by g(n) for any constants c1,c2.
• We generally neglect lower order terms for analyzing the complexity of algorithm. eg( an²+bn+c)  could be written as O(n²))

Floors and ceilings:
floor(x) =  is the largest integer not greater than x and ceiling(x) =  is the smallest integer not less than x.
for example floor(9.6)=9 and ceiling(9.6)=10.

Complexity Analysis

I am presenting simple comlexity analysis of algorithms for that I'll use Insertion sort algorithm:

Insertion sort algo:

Insertion Sort(Array A)


 for int j=2 to A.length{    // it will loop through for n times, cost= c1*n

  key=A[j]   // it will loop for n-1 times, cost= c2*(n-1)

  i=j-1;   // it will loop for n-1 times, cost= c3*(n-1)    

  while( i>0 && A[i]> key){  // depends on condition being true, cost= c4 *(∑ tj where j=2 to n)

  A[i+1]= A[i];   //cost= c5 *(∑ tj-1 where j=2 to n)

  i--;   // cost= c6 *(∑ tj-1 where j=2 to n)

 }

  A[i+1]=key;   // cost= c7 *(n-1)

}

where all c1,c2 etc are constants, so the total time to excute this algorothms would be:
T(n)= c1*n+ c2*(n-1)+ c3*(n-1)+c4 *(∑ tj where j=2 to n)+ c5 *(∑ tj-1 where j=2 to n)+ c6 *(∑ tj-1 where j=2 to n)+c7 *(n-1)

In the worst case the inner while loop will execute for each element and hence will sum up as:
(∑ tj-1 where j=2 to n) = 1+2+3+4+-------+n-1 =  n*(n-1)/2
that will be equal to n^2.

So  now T(n)= c1*n+ c2*(n-1)+ c3*(n-1)+c4 *(n^2)+ c5*(n^2)+ c6*(n^2)+c7 *(n-1)

and since n^2 is the maximum term , ignoring lower order terms will give us :
T(n)=O(n^2).

This approach is very useful in analysis of all the algorithms which uses loops and gives basic idea of how to derive complexity.
Post comments if you face any issue to analyze complexity or any problems in this method to follow.