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.