Intro To Algorithms

ECE 242 Fall 2007

Data Structures and Algorithms in Java Analysis of Algorithms

ECE242 Fall 2007

Data Structures in Java, Prof. Mettu

Analysis of Algorithms • How do we compare two implementations of the same interface? • We need to account for all possible inputs. • Our performance measure should be conservative.

ECE242 Fall 2007

Data Structures in Java, Prof. Mettu

“Asymptotic” Running Time How do we characterize the running time of a method? public boolean contains(int x) { int i = 0; while ((i < next) && (data[i] != x)) { i++; } return (i != next); }

Just count number of time units utilized; here the parameter is the size of the collection. ECE242 Fall 2007

Data Structures in Java, Prof. Mettu

“Worst-case” Analysis • Which implementation is better? • Any single measure of running time should describe performance over all possible inputs.

• Worst-case reasoning is conservative, and can serve as a baseline measure for comparing implementations.

ECE242 Fall 2007

Data Structures in Java, Prof. Mettu

Defining Running Time We can parameterize the running time of a method by its input. public int sum(int n) { int sum = 0; for (int i = 1; i <= n; i++) sum += i; return sum;

public int sum(int n) { return (int) n*(n+1)/2; }

}

ECE242 Fall 2007

Data Structures in Java, Prof. Mettu

Defining Running Time We can parameterize the running time of a method by its input. public int sum(int n) { int sum = 0; for (int i = 1; i <= n; i++) sum += i;

public int sum(int n) { return (int) n*(n+1)/2; }

return sum; }

n+n+n ECE242 Fall 2007

Data Structures in Java, Prof. Mettu

Defining Running Time We can parameterize the running time of a method by its input. public int sum(int n) { int sum = 0; for (int i = 1; i <= n; i++) sum += i;

public int sum(int n) { return (int) n*(n+1)/2; }

return sum; }

n+n+n ECE242 Fall 2007

Data Structures in Java, Prof. Mettu

3

Big-O Notation We would like to ignore platform-specific details.

r(n) = O(f (n))

⇔

Asymptotic Runtime

Allows for slack in bound

∃c, n0 : ∀n :: n > n0 → r(n) ≤ c · f (n) ECE242 Fall 2007

Data Structures in Java, Prof. Mettu

Why Big-O Notation? 2.55n

runtime

7

n

.75n

5 1 input size ECE242 Fall 2007

Data Structures in Java, Prof. Mettu

Characterizing an Algorithm public void some_method() { <statement 1>; <statement 2>; ...

characterize space/running time

r(n)

}

prove upper bound

r(n) = O(f (n)) ECE242 Fall 2007

Data Structures in Java, Prof. Mettu

Static vs. Dynamic Collections Which is faster? Why? Method

Array-based Dynamic Implementation Implementation

add() remove() contains() size() ECE242 Fall 2007

Data Structures in Java, Prof. Mettu

Static vs. Dynamic Collections Which is faster? Why? Method

add()

Array-based Dynamic Implementation Implementation

O(n)

remove() contains() size() ECE242 Fall 2007

Data Structures in Java, Prof. Mettu

O(1)

Static vs. Dynamic Collections Which is faster? Why? Method

Array-based Dynamic Implementation Implementation

add()

O(n)

O(1)

remove()

O(n)

O(n)

contains() size() ECE242 Fall 2007

Data Structures in Java, Prof. Mettu

Static vs. Dynamic Collections Which is faster? Why? Method

Array-based Dynamic Implementation Implementation

add()

O(n)

O(1)

remove()

O(n)

O(n)

contains()

O(n)

O(n)

size() ECE242 Fall 2007

Data Structures in Java, Prof. Mettu

Static vs. Dynamic Collections Which is faster? Why? Method

Array-based Dynamic Implementation Implementation

add()

O(n)

O(1)

remove()

O(n)

O(n)

contains()

O(n)

O(n)

size()

O(1)

O(1)

ECE242 Fall 2007

Data Structures in Java, Prof. Mettu