Best , Worst and Average Cases

Best , Worst and Average Cases
Ex. 10:
Insertion an element x to sorted array A[0..n-1], where all the
elements of the array are sorted in increasing order before and after
insertion process.
Algorithm Insertelement (A, n, x):
Input: Sorted array A[0..n-1] with size n and the required element x to be
inserted.
Output: Sorted array A[0..n].
1. for i ? n-1 down to 0 while i >= 0 and x < A[i]
2. A[i+1] ?A[i]
3. end for
4. A[i+1] ?x
5. n? n+1
The instance characteristics of this problem is n.
Time complexities (step counts):
1)) Best case:
When x is greater than all elements of A.
1. for …………………… 1
2. statement inside for .…………. 0
3. insert x …………………… 1
4. increment the size n ………….. 1
T B
Insertelement (n) = 3
2)) Worst case:
When x is smaller than all elements of A.
1. for …………………… [(n-1)-0+1] +1 = n+1
2. statement inside for .…………. n
3. insert x …………………… 1
4. increment the size n ………….. 1
T W
Insertelement (n) = 2n+3
2
3)) Average case:
It is the average of complexities of insertion cases for all positions.
T Av
Insertelement (n)
1
2( ) 3
0
+
- +
=

=
n
n i
n
i
The best and worst cases are subset from the average case.
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Asymptotic Notations
The process of determining step counts of an algorithm was proved
that it is high difficult process, thus Asymptotic Notations are used
in computing space and time complexities of an algorithm, they are
estimation of the complexities in real but they are easer than step counts.
Asymptotic Notations give formula type without interesting with its
details.
1)) Upper Bound Notation (Big-Oh):
f(n) is O(g(n)) if there exist positive constants c and n0 where (c>0),
(n0 ³0) such that f(n) £ c × g(n) for all n ³ n0.
f(n): is space function S(n) or time function T(n).
This definition shows that function f(n) grows no faster than c.g(n).
Theorem:
If f(n) m
m
m
m = a + a n + + a n - + a n
-
1