I'm trying to figure out how to give a worst case time complexity. I'm not sure about my analysis. I have read nested for
loops big O is n^2
; is this correct for a for
loop with a while
loop inside?
// A is an array of real numbers.
// The size of A is n. i,j are of type int, key is
// of type real.
Procedure IS(A)
for j = 2 to length[A]
{
key = A[ j ]
i = j1
while i>0 and A[i]>key
{
A[i+1] = A[i]
i=i1
}
A[i+1] = key
}
so far I have:
j=2 (+1 op)
i>0 (+n ops)
A[i] > key (+n ops)
so T(n) = 2n+1?
But I'm not sure if I have to go inside of the while
and for
loops to analyze a worse case time complexity…
Now I have to prove that it is tightly bound, that is Big theta.
I've read that nested for
loops have Big O of n^2
. Is this also true for Big Theta? If not how would I go about finding Big Theta?!
**C1= C sub 1, C2= C sub 2, and no= n naught all are elements of positive real numbers
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 ≤ nThis 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 = 1Hence 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
Tell me what you thing guys… I'm trying to understand this material and would like y'alls input!
Best Solution
You seem to be implementing the insertion sort algorithm, which Wikipedia claims is O(N^{2}).
Generally, you break down components based off your variable N rather than your constant C when dealing with BigO. In your case, all you need to do is look at the loops.
Your two loops are (worse cases):
The outer loop is O(N), because it directly relates to the number of elements.
Notice how your inner loop depends on the progress of the outer loop. That means that (ignoring offbyone issues) the inner and outer loops are related as follows:
So the total number of times that
/*action*/
is encountered is (N^{2}  N)/2, which is O(N^{2}).