asymptotic_analysis.md

Asymptotic Analysis

Algorithms

Programs = Algorithms + Data Structures

• Niklaus Wirth, Turing Award winner

An algorithm is a method or a process to solve a problem

• A problem can be solved by many different algorithms

When we're implementing the operations in data structures, we're actually designing and implementing algorithms

• E.g., insert and remove in AList

How do we measure and compare the efficiency of different algorithms?

1. Empirical comparison (run programs)
2. Asymptotic algorithm analysis
   • Running time is expressed as a function T on input size n, i.e., T(n)
   • Showing the growth rate of running time depending on n

Time Complexity

Big-Oh notation

Definition: For T(n) a non-negative valued function, T(n) is in the set O(f(n)) if there exist two positive constants c and n0 such that T(n) <= c f(n) for all n > n0.

Indicates an upper bound of a function

More Time Complexity Examples

int n = 10;
// T(n) = O(1)

int sum = 0;
for (int i = 1; i <= n; i++)
    sum += n;
// T(n) = O(n)

int sum = 0;
for (int j = 1; j <= n; j++)
    for (int i = 1; i <= n; i++)
        sum++;
// T(n) = O(n^2)

int a[n];
for (int k = 0; k < n; k++)
    a[k] = k;
// T(n) = O(n)

int sum1 = 0;
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
        sum1++;
// T(n) = O(n^2)

int sum2 = 0;
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= i; j++)
        sum2++;
// T(n) = O(n^2)

int sum1 = 0;
for (int k = 1; k <= n; k *= 2)
    for (int j = 1; j <= n; j++)
        sum1++;
// T(n) = O(n log n)

int sum2 = 0;
for (int k = 1; k <= n; k *= 2)
    for (int j = 1; j <= k; j++)
        sum2++;
// T(n) = O(n)

Practical Examples in AList

remove(): In the worst case, shifting n-1 elements, i.e., T(n) = O(n)

prepend(it): In the worst case, shifting n elements, i.e., T(n) = O(n)

removeFirst(): Shifting n-1 elements, i.e., T(n) = O(n)

removeLast(): No shifting is needed, i.e., T(n) = O(1)

removeElement(it):

• Traverse through the list: if it is observed, call remove to remove the element
  • In the worst case, n iterations for traversal, in each iteration O(n) for removal
  • In total O(n^2)
• Alternative solution on Piazza with O(n) running time

HW 4

Sorted lists: elements are sorted by their value in the list

1. void putElement(const E &it)

2. int findInsertPosition(SortedList<int> list, int target)