First of all, you should know the basic details of the program and must decide the case of time complexity.
I will consider the worst case.Let us try and find out complexity of a oblivious sort algorithm:
let us assume that array A[] contains reverse sorted(unsorted in worst case) list of integers.
The pseudo-code for the oblivious-sort algorithm is something like :
n is the length of the array.
OBVILIOUS-SORT
for(i=0;i<n;i++)
{
for(j=0;j<n-1;j++)
{
if(A[j+1]<A[j])
{
Swap(j+1,j)
}
}
}
Now let us consider each aspect.
1)Consider the
first for loop:
for(i=0;i<n;i++) :
i=0 will run only once.
i<n will run n+1 times.
i++ will run n times.
so the net cost is 1+(n+1)+n = 2n+2
2)Consider the
2nd for :
for(j=0;j<n-1j++)
Also let us consider this individually,without taking the effect of previous for loop.
j=0 will run only once.
j<n-1 will run n times
j++ will run n-1 times
so the net cost for 2nd for loop alone is 1+n+n-1 = 2n
3) Swapping is a linear time algorithm, it will run only once per iteration.
However since both the loops are nested, the second for loop will run 2n+2-1 times.(last i++ will beak the first for loop).
Multiplying its own cost to that of first for loop.So,
T(n)= (2n+1)(2n(1)).. cost of first for loop*(cost of second for loop*(cost of swap))
T(n)=(2n+1)(2n)
T(n)=4n[SUP]2[/SUP]+2n
T(n)=O(n[SUP]2[/SUP]).
So this obvilious sort has time complexity of
O(n[SUP]2[/SUP]).
This can be simplified:In asymtotic analysis, when we consider
O notations, we never go for the lower order terms.
O(n[SUP]2[/SUP])=4n[SUP]2[/SUP]+3n+2
O(n[SUP]2[/SUP])=10n[SUP]2[/SUP]+50n
so in both the cases, the final time complexity in terms of O is n[SUP]2[/SUP].
the easiest way, is to look at the number of loops and the nested loop.
in the above sort algorithms, there are 2 for loops and are nested which will run for n times each, hence the time complexity is n*n=n[SUP]2[/SUP].
You can write a code based on this, and run this on asymtotic inputs at periodic intervals(100,200,300, till you get bored), and take the time required to complete the sorting procedure. Plot a graph (you can use MS Excel for it),you can see the obvious n^2 characteristics.
-Thank you.