Hi Neha,
calculating time complexity of loop quite difficult. Hope the below article will help u to understand how to calculate time complexity.
To find the T(n)
I looked at the values of j
and looked at how many times the while loop executed:
values of J: 2, 3, 4, ... n
Loop executes: 1, 2, 3, ... n
Analysis:
Take the summation of the while loop executions and recognize that it is (n(n+1))/2
I will assign this as my T(n)
and prove it is tightly bounded by n^2
.
That is n(n+1)/2= θ(n^2)
Scratch Work:
Find C1, C2, no є R+ such that 0 ≤ C1(n^2) ≤ (n(n+1))/2 ≤ C2(n^2)for all n ≥ no
To make 0 ≤ C1(n) true, C1, no, can be any positive reals
To make C1(n^2) ≤ (n(n+1))/2, C1 must be ≤ 1
To make (n(n+1))/2 ≤ C2(n^2), C2 must be ≥ 1
PF:
Find C1, C2, no є R+ such that 0 ≤ C1(n^2) ≤ (n(n+1))/2 ≤ C2(n^2) for all n ≥ no
Let C1= 1/2, C2= 1 and no = 1.

show that 0 ≤ C1(n^2) is true
C1(n^2)= n^2/2
n^2/2≥ no^2/2
⇒no^2/2≥ 0
1/2 > 0
Therefore C1(n^2) ≥ 0 is proven true!

show that C1(n^2) ≤ (n(n+1))/2 is true
C1(n^2) ≤ (n(n+1))/2
n^2/2 ≤ (n(n+1))/2
n^2 ≤ n(n+1)
n^2 ≤ n^2+n
0 ≤ n
This we know is true since n ≥ no = 1
Therefore C1(n^2) ≤ (n(n+1))/2 is proven true!

Show that (n(n+1))/2 ≤ C2(n^2) is true
(n(n+1))/2 ≤ C2(n^2)
(n+1)/2 ≤ C2(n)
n+1 ≤ 2 C2(n)
n+1 ≤ 2(n)
1 ≤ 2nn
1 ≤ n(21) = n
1≤ n
Also, we know this to be true since n ≥ no = 1
Hence by 1, 2 and 3, θ(n^2 )= (n(n+1))/2 is true since
0 ≤ C1(n^2) ≤ (n(n+1))/2 ≤ C2(n^2) for all n ≥ no
Reference : http://stackoverflow.com/questions/656745/howdoifindthetimecomplexitytnandshowthatitistightlyboundedbigt