CSCI311.moreTime

CSCI311
More on Time

More examples for calculating T(n) [to ultimately get O(n)]

Consider times of "inner parts"



for (i= 1; i <= n, i++) 

	for (j= 1; j <= n, j++) 

	 	a[i,j] = x;
	 
T(n) = 	_{i=1 to n}   [T(s1)]         (where T(s1) is the inner "j" loop)

		T(s1)=	_{j=1 to n}   1 = n


So	

T(n) = _{i=1 to n}   [T(s1)]  = _{i=1 to n}   n = n[_{i=1 to n}   1] = n*n
=n²


So, O(n²)

notice it is i that is changing in the summation, not n.

This is why we can bring n "out".

In general, _{i=1 to n} c*i = c[_{i=1 to n} i]

Another useful fact:

Obviously, _{i=1 to n} 1 = n

In general, _{i=a to n} 1 = n - a + 1

specifically: _{i=2 to n} 1 = n - 2 + 1 = n - 1

Best, Worse and Average Operation Counts

Section 2.3.3

An example:

This program finds the minimum value and then returns (writes out) the rest of the array. (this is not in Java; I am using it only to consider time performance)

procedure TrailMin Read(Entry[1]) Mindex = 1 for i=2 to n do Read(Entry[i]) if Entry[i] < Entry[Mindex] then Mindex = i for i=Mindex + 1 to n do Write(Entry[i]) Consider Read, Write, if, assignment all to have time 1

T(n) = 2 + _{i=2 to n} 2 + _{i=Mindex+1 to n} 1

= 2 +2(n - 2 + 1) + (n - (Mindex + 1) + 1)

= 2 + 2n - 4 + 2 + n - Mindex = 3n - Mindex

Clearly, Mindex may be a function of n itself.

(Remember, Mindex is the index of the minimum - not the calculations to get there)

Consider

*Worst case analysis

*Statistically average case analysis

Worst case analysis
Remember, Mindex is the index of the minimum
minimum is first index, Mindex = 1; T(n) = 3n -1
Statistically average case analysis

Mindex can range from 1 to n equally likely
P(any index) = 1/n

In general:
E_{ExpectancyOfaThing} = _{(over things)} (thing * Probability_thing)

E_Mindex = _{(all x)} (Mindex * P[Mindex])

= _{Mindex = 1 to n} (Mindex * P[Mindex])

= 1/n _{Mindex= 1 to n} (Mindex)

= 1/n * n(n+1)/ 2 // cancel n's

= (n+1)/2

So, Statistical average
T(n) = 3n - (n+1)/2 = 6n/2 - (n+1)/2 = (5n-1)/2

O(?) for both?

Compare (in general, when we say log in this course we will mean log₂ - whether we say so explicitly or not. SO
I strongly suggest using values of n that are powers of 2 to see the patterns since log₂ are integers for powers of 2):

n² n nlog₂n log₂n n^-1 n/log₂n 2^log2ⁿ (that was mean of me - look here to help with logs)

Actually we will look at these later in Chapter 3 (Tables and Figures of text there help)

CSCI311 More on Time

Best, Worse and Average Operation Counts

CSCI311
More on Time