JAVA HeapSort

import java.io.*;
class heap_sort
{
static int heapsize;
public static void main(String args[])throws IOException
{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
System.out.println("Heap size??");
int n=Integer.parseInt(br.readLine());
int i,a[]=new int[n],temp;
for(i=0;i<n;i++)
a[i]=Integer.parseInt(br.readLine());
heapsize=a.length;
maxheap(a);
for(i=n-1;i>=1;i--)
{
temp=a[0];
a[0]=a[i];
a[i]=temp;
heapsize--;
maxheapify(a,0);
}
}
public static void maxheap(int a[])
{
int i;
for(i=(heapsize-1)/2;i>=0;i--)
a=maxheapify(a,i);
}
public static int[] maxheapify(int a[],int i)
{
int l=2*i+1;
int r=2*(i+1);
int largest,temp;
if(l<heapsize&&a[l]>a[i])
largest=l;
else
largest=i;
if(r<heapsize&&a[r]>a[largest])
largest=r;
if(largest!=i)
{
temp=a[i];
a[i]=a[largest];
a[largest]=temp;
maxheapify(a,largest);
}
return a;
}
}

How to calculate the time complexity???

In this post I am going to discuss how to calculate time complexity of the algorithms.Firstly I am going to take up a non-recursive,simple algorithm and then look at the recursive ones.
What can be simpler than an algorithm to add two numbers.The method Sum does it for us:
1.Sum(a,b)
2.    s=a+b         // c1*1
3.    return s        //c2*1

The comments indicates the total time required by the respective statements at run-time.c1 and c2 are the time required to process the statement.It depends upon the processor speed which may be different for different computers while the 1's is the number of times(i.e. frequency) ,the statement is executed. Hence , the total time required is c1+c2 which is equal to some constant c.In algorithimic notations we express this constant function as O(1).

Now lets look at another algorithm.This time,the sum of first n natural numbers.

1.Nat_Sum(n)
2.    s=0                //c1*1
3.    for i=1 to n     //c2*n
4.          s=s+i        //c3*n 
5.    return s           //c4*1

Now just count the total time required.Its c1+c4+n(c2+c3) which is equal to some other constants e1+e2(n).
Hence in Big O notation it is expressed as O(n) removing all constants.So it is linear algorithm.

Similarly when there are two nested loops, the time complexity is generally O(n^2).
We will look at the recursive algorithms in the next post.