Algorithm Complexity
> Click or hit Control-Enter to run Example.main above
At The Limit
We’re usually want to analyze an algorithm in the general case, rather than for a specific set of input.
-
How does the algorithm perform on arbitrarily difficult or large inputs?
-
What are the best, average, and worst-case running times?
-
How is the algorithm’s performance related to its inputs?
> Click or hit Control-Enter to run Example.main above
Analyzing Our Brute Force GCD
Given M and N, for our brute force GCD algorithm:
-
What’s the worst case? Two large prime numbers.
-
What’s the best case? One input is one, or divides the other.
-
What’s the average case? Let’s guesstimate half of the larger of M and N 1.
-
How is its performance related to its inputs? It grows with the smaller of M or N.
> Click or hit Control-Enter to run Example.main above
Big-O Notation
Big-O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity.
Put another way: we want to estimate what happens as the problem gets really, really hard.
Big-O Notation
O(1)
int[] myArray = new int[1024];
int getArrayValue = myArray[10]; // This is constant timeO(1) is sometimes called constant time.
Life is good and livin' is easy. But we’re usually not this lucky.
O(n)
int[] myArray = new int[1024];
int sum = 0;
// A single loop through an array is usually O(n)
for (int arrayValue : myArray) {
sum += arrayValue;
}O(n) is still not bad.
Frequently we have to see each value in an array or other data structure at least once, so sometimes O(n) is the best we can do.
Big-O Notation
O(n)
int[] myArray = new int[1024];
for (int arrayValue : myArray) {
if (arrayValue == lookingFor) {
break;
}
}What about the example above?
-
Best case: it’s the first element
-
Worst case: it’s the last element
-
Average case: O(n / 2), which we usually simplify to just O(n)
O(n^2)
boolean isSorted(int[] array) {
for (int i = 0; i < array.length; i++) {
for (int j = i; j < array.length; j++) {
if (array[j] < array[i]) {
return false;
}
}
}
return true;
}Now things are getting bad.
-
Best case: the unsorted element is at the beginning
-
Worst case: the array is sorted
-
Average case: O(n^2)
Big-O Notation
O(log n) and O(n log n)
The logarithmic growth rates are usually caused by features of problems that we haven’t seen yet—but will soon.
Dumb Algorithm, Clever Algorithm
A dumb algorithm can move a problem up in the runtime categorization: for example, from O(n) to O(n^2). (Our sort test is dumb. The problem is O(n).)
A smart algorithm can move a problem down in the runtime categorization: for example, from O(n^2) to O(n log n). (Euclid’s Method GCD is smart. The problem is O(log(N)).)
Big-O Notation
Does P == NP?
The P versus NP problem is a major unsolved problem in computer science. It asks whether every problem whose solution can be quickly verified can also be quickly solved.
Whether P == NP is one of the deepest unsolved mysteries in mathematics and computer science.
Simply put, are some problems just harder than others—or have we just not found good ways of solving them yet.
Sudoku Turns Out to be Interesting 1
Announcements
-
MP4 is out and due in less than two weeks. The early deadline is Monday. Please get started. MP4 is not easy.
-
Continue to communicate with the course staff about the strike as needed. We’re trying to keep everything up and running.
-
My office hours continue today at 11AM in the lounge outside of Siebel 0226.