Big O and Lists
Notes adapted from Zach Tomaszewski
- Do multiple algorithms solve the same problem?
- Do multiple algorithms run in the same amount of time?
- Do multiple algorithms use the same amount of memory?
Benchmarking is the act of timing how long it takes for a particular piece of code to run. It's possible to measure
- Clock time
- Processor time
- Memory consumption
However, there are many areas where benchmarking can give incorrect results
- Language factors (start-up time, garbage collection, compiler optimizations)
- Code differences (loop types, methods used, etc)
- Hardware factors
- Data set size
- Timing accuracy
Benchmarking is not a good measure of algorithm performance. We need something more abstract.
What constitutes a single step?
x = x + 4
x += 4
x = x - 8 * 2
swap(x, y)- How does an algorithm perform under stress? (i.e. addition of more data to process)
- Algorithms can be categorized by growth rate
- Ignore the finer details
- Uses a single measure
- Measure is a function, so informative over a range of possible values
- Guaranteed upper bound of worse-case
- Good way to compare different algorithms
- Start by counting "steps", but then drop the details to see the bigger picture
Assuming each statement takes 1 "step" to run, what's the runtime of the following algorithm?
for (int k = 0; k < n; k++) {
//statement 1
//statement 2
//...
//statement 5
}
//...25 more statements...
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
//statement 1
//statement 2
}
}- Let n be the size of the data
- T(n) = O(f(n)) as n -> ∞ iff there exist constants n0 >= 0m and c > 0 such that for all n > n0, T(n) <= cf(n)
- T(n) = O(f(n)) shortcut notation for T(n) ∈ O(f(n))
- T(n) = 2n^2 + 5n + 25
- T(n) = O(f(n)) iff T(n) <= cf(n) for some n > n0 and c
- T(n) <= cf(n) ... 2n^2 + 5n + 25 <= cf(n)
- Select n0 = 5 and c = 4 and f(n) = n^2 (or other higher values)
- T(n) <= cf(n): 2n^2 + 5n + 25 <= 4 * n^2
- For n = n0 = 5: 50 + 25 + 25 <= 4 * 25. (100 <= 100)
- For any higher n (such as 6): 72 + 30 + 25 <= 4 * 36. (127 <= 144)
- And so on
- Therefore: T(n) = O(n^2) for c = 4 and n0=5
- Big-O is upper-bound (worse-case)
- Big-Ω (omega) is lower-bound
- Big-Θ (theta) bounded by upper and lower-bound
- Also used for space growth and generally for other functions
- Asymptotic (that is, usually as n -> ∞)
- Can have more than one variable, (n, m, etc)
- Given T(n) = 2n^2 + 5n + 25
- Drop all lower-order terms: T(n) = O(2n^2)
- Drop any coefficients: T(n) = O(n^2)
- Usually it's easy to infer Big-O by looking at the code, but it can get tricky (recursion)
Summary: Big-O tells us the algorithm won't grow any faster (get any worse) than a given f(n), no matter how many more processed elements are added.
/**
* Search through array for target, return the index of the target or -1 if target is not in the array.
* @param x Array to search through.
* @param target Value to search for.
* @return The index of the target or -1.
*/
public static int search(int[] x, int target) {
for (int i = 0; i < x.length; i++) {
if (x[i] == target) {
return i;
}
}
return -1;
}- What corresponds to n?
- What's the best/worst/average case in terms of n?
- Big-O?
/** Prints the given array forward and then backwards. */
public static void backAndForth(int[] nums) {
//forward
for (int n : nums) {
System.out.print(n);
System.out.print(" ");
}
System.out.println();
//backwards
for (int i = nums.length - 1; i >= 0; i--) {
System.out.print(nums[i]);
System.out.print(" ");
}
System.out.println();
}- Big-O?
/** Prints a box of #s of width * height. */
public static void drawBox(int width, int height) {
for (int row = 0; row < height; row++) {
for (int col = 0; col < width; col++) {
System.out.print('#');
}
System.out.println();
}
}- What corresponds to n here?
- Big-O?
- As a square (n == m)
/** Prints 5 boxes of the given size. */
public static void drawBoxes(int size) {
for (int i = 0; i < 5; i++) {
drawBox(size, size);
System.out.println();
}
}- What happens if we consider drawBox at a single step (O(1))?
/** Prints the given number of boxes. */
public static void drawBoxes(int many) {
for (int i = 0; i < many; i++) {
drawBox(10, 10);
System.out.println();
}
}- Big-O? O(n) (since drawBox is a constant cost now: 10 x 10)
- If we replaced drawBox(10,10) with drawBox(many, many)? O(n^3)
/** Returns whether there are any repeated values in the given array. */
public static boolean findDuplicates(int[] nums) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] == nums[j]) {
return true;
}
}
}
return false;
}- Big-O?
- Example: Binary search
- Look for loops, since they act as "multipliers" on their contained statements.
- Drop constants
- Recursion can also cause Big-O growth
- Common Big-Os: O(1), O(log n), O(n), O(n log n), O(n^2), O(n^3), O(2^n), O(n!)
- Beginner's guide to Big-O Notation: http://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/
- Constants are dropped but can be very big in practice... consider the following:
- 2000n = O(n) vs 2n^2 = O(n^2)
- n=10 ... 20,000 vs 200
- n=1000 ... 2 million vs 2 million
- n = 10,000 ... 20 million vs 200 million
- n = 1,000,000 ... 2 billion vs 2e+12
- Usually upper-bound of worse-case, but sometime worst case is rare in practice (quicksort)
- Resizable
- Generic
- Autoboxes primitive types
Some of the common operations include
- boolean add(E e)
- void add(int index, E element)
- void clear()
- boolean contains(Object o)
- E get(int index)
- E remove(int index)
- boolean remove(Object o)
- int size()
- Backed by an array
- As the size of an ArrayList grows, new arrays must be created to compensate
What is the Big-O for a list built on an array?
- Adding to the list - O(n)
- Getting from the list - O(1)
- Removing from the list - O(n)
- Getting the size - O(1)