Asymptotic Notation and Analysis 

Introduction

    What can computers do?
        Count:
                Add: Numerical Analysis
                Compare:
                    Search
                    Order

    What is a Data Type?
        Machine representation of numbers

    What is Data Structure?
        Abstract Data Type:
            Data
            Operations
        Data Structure: Implementation
        Typical Uses: Data files etc.

What you need to remember about data structure:
    ADT: name and methods
        List of DS associated with ADT
            idea of implementation
            important algorithms
            running time or complexity
            storage

Running Time or Cost of an Algorithm

Difficulty of measuring running time:

As CS programmers we are hired to solve big problems.

Running time vs Problem size:

What is problem size?  Data size or number of basic elements.

Running time

Example:

                     int arrayFind(x, A)
            // input: element, x and array A
            // output: index i such that  x == A[i]
                i=0
                while i < n    // length of A
                    if x =A[i] then return i
                    else i++
                return -1 // fail to find

Average and worst case are different.

What about something even more general?

Asymptotic Notation:

Definition of Big O:

f is O(g) <=> Exist integer N and real constant c so that f(n) < cg(n) for all n>N

Intuitively: g is an upper bound for f

This gives times in terms of Order: logarithmic, linear, quadratic, exponential.
Comparison of different families

Practical examples:

Others asymptotic bounds:

Are the examples above also big Theta?

 Asymptotic Analysis:

Consider prefix average: A[i] = Average of {  X[0] to X[i] } = Sum up to i of X[j]/i+1

Algorithm: prefixAvg1(X)

Let A be an array
for i = 0 to n -1 do
a = 0
for j = 0 to i do
    a = a + X[j]
A[i] = a/(i+1)
return A

What is the asymptotic running time?


Algorithm: prefixAvg2(X)

Let A be an array
s = 0
for i = 0 to n -1 do
 s = s + X[j]
A[i] = s/(i+1)
return A

What is the asymptotic running time of this one?