Time Complexity
Just count the number of steps of the program with the input size n. Lets understand by the example
bubble_sort(int a[])
{
int n=length(a);
int temp;
for (i=0; i< n; i++)
for (j=0; i<n; j++)
{
if (a[i] > a[j])
{
temp = a[I];
a[i] = a[j];
a[j] = temp;
}
}
}
Because of the for statement at line 3, the block between lines 4 and 12 gets run exactly N times, where N is the length of the list. This block is itself a for loop that runs exactly n times, so the if block between lines 6 and 10 gets executed N^2 times in all.
So
Line 1-2: Executed once
Line 3: Executed once (sets i = 1 at the beginning)
Line 4: Executed n times (sets J = 1 once per value of I)
Line 5: Executed n^2 times
Line 6: Executed n^2 times
Line 7: Executed between 0 and n^2 times.
Line 8: Executed between 0 and n^2 times.
Line 9: Executed between 0 and n^2 times.
Line 10: Executed n^2 times (increments j and jumps to line 5)
Line 11: Executed n times (increments i and jumps to line 4)
So if we count the number of times a line gets executed, we have something between 6N^2+2N+3 (worst case), and 2N^2+2N+3 (best case). Which tells us that as the N increases then the time of the execution is proportional to N^2 which means time complexity of the program is O(n^2).
Space Complexity
The space complexity of an algorithm is measured as the maximum amount of space used at any one time. In this case we need array a which is of the order n and one temp variable for the swap. So the space complexity of the above program is n+1 or ~n.
