We talked about Θ last class. In particular, we said that when we say "T(n) = Θ(n^2)", it means that T(n) grows like" n^2, or its curve "has the same shape".
There are several rules for how you can manipulate and do arithmetic with Θ's. And these rules will allow us to analyze the performance of algorithms analytically.
So, for example, this says Θ(32 n^2) = Θ(n^2) Because of this, we never say "Algorithm A's worst cast running time is Θ(32 n^2)". We'd simply say"Algorithm A's worst cast running time is Θ(n^2)".
So, for example, this tells us that Θ(n^3 + 3 n) = Θ(n^3). In fact, by repeatedly applying this rule, you should see that the dominant term is the only one that matters. For example: we'd never say "Algorithm A's running time is Θ(3 n^2 + 12 n + 7)". We'd apply this rule to say that the above is equivalent to Θ(3 n^2), which is the fastest growing term, then we'd apply rule 1 to say that this is equivalent to Θ(n^2). So we'd say "Algorithm A's running time is Θ(n^2)".
Consider the following algorithm for finding the midpoint of (x1,y1) and (x2,y2):
double xm, ym;
xm = (x1 + x2)/2;
ym = (y1 + y2)/2;
What's the running time for this? Well, certainly each statement takes constant time, which means Θ(1).
double xm, ym; <----- Θ(1)
xm = (x1 + x2)/2; <----- Θ(1)
ym = (y1 + y2)/2; <----- Θ(1)
+______________________________________________________
Θ(1) + Θ(1) + Θ(1) = Θ(3) = Θ(1)
Our algorithm for midpoints runs in time Θ(1), i.e. in constant time.
Consider the following algorithm for adding up all the integers from 1 to n^2.
int sum = 0, i = 1, B;
B = n*n;
while(i < B)
{
sum = sum + i;
i++;
}
Let's try to add up costs again:
int sum = 0, i = 1, B; <----- Θ(1)
B = n*n; _ <----------- Θ(1)
while(i < B) \
{ |
sum = sum + i; <------------ B * "cost of 1 loop iteration"
i++; | = B*(Θ(1) + Θ(1) + Θ(1))
} _/
Now, looking at the program, you see that B is in fact just n^2, so simplifying our answer we get:
T(n) = Θ(1) + Θ(1) + n^2*(Θ(1) + Θ(1) + Θ(1))
= Θ(2) + n^2 * Θ(3)
= Θ(1) + n^2 * Θ(1)
= Θ(1) + Θ(n^2*1)
= Θ(1 + n^2)
= Θ(n^2)
Here is the most naive version of Bubblesort for an array A of n integers. Let's try analyzing it:
int i = 1; <------------------------------------ Θ(1)
while (i < n) <----------------
{ |
int j = 1; |
while (j < n) |
{ |
if (A[j - 1] > A[j]) |
{ | (n - 1) * "cost of 1 loop iteration"
int t = A[j]; |
A[j] = A[j - 1]; |
A[j - 1] = t; |
} |
j++; |
} |
i++; |
} <------------------------
So, the question is what is the cost of an iteration through the outer loop? Well,
while (i < n) <---------------- Θ(1)
{
int j = 1; <---------------- Θ(1)
while (j < n) <---------
{ |
if (A[j - 1] > A[j]) |
{ |
int t = A[j]; | (n - 1) * "cost of 1 loop iteration"
A[j] = A[j - 1]; |
A[j - 1] = t; |
} |
j++; |
} <--------------------
i++;<------------------------ Θ(1)
}
So, we have T(n) = Θ(1) + (n-1)*(Θ(1) + Θ(1) + (n - 1)*"cost of 1 inner loop iteration" + Θ(1)), which we can simplify to T(n) = Θ(1) + (n-1)*(Θ(1) + (n - 1)*"cost of 1 inner loop iteration"). Then, what about the cost of one inner loop iteration? Well, it's Θ(1) for testing the if-condition, then possibly Θ(1) + Θ(1) + Θ(1) if the if-condition is true, then Θ(1) for incrementing j. So, it's either Θ(2) or Θ(5), but either way we can simplify to Θ(1). In other words, regardless of whether or not we swap, we can bound the time required by 1 inner loop iteration between two constants. Thus, the total cost for BubbleSort is
T(n) = Θ(1) + (n-1)*(Θ(1) + (n - 1)*Θ(1))
= Θ(1) + (n-1) * Θ(1) + (n-1)*(n-1) * Θ(1)
= Θ(1) + Θ(n-1) + Θ((n-1)*(n-1))
= Θ(1) + Θ(n) + Θ(n^2 - 2*n + 1)
= Θ(1) + Θ(n) + Θ(n^2)
= Θ(n^2)
That's a lotta work ... except that we don't have to be so pedantic. When you see several steps, each of which takes constant time, just say the whole thing is Θ(1). When you're looking at a loop, don't worry about the overhead of setting the loop counter, etc. That's all constant time, so it's gonna be dominated by the time inside the loop, which will grow with the number of times we iterate with the loop.
So far we've learned about Θ. When we say
T(n) = Θ(f(n))
we're saying that T(n) grows like f(n) grows. Often times, however, we're simply not able to say anything as concrete as that. For example, consider "BubbleSortV2.0", which incorporates the following observation: If we do a full pass through the array in the inner loop and never make a swap, then we know the array is sorted and we can stop. This improved bubble sort looks like this:
int i = 1, swapcount = -1;
while (i < n && swapcount != 0)
{
swapcount = 0;
int j = 1;
while (j < n)
{
if (A[j - 1] > A[j])
{
int t = A[j];
A[j] = A[j - 1];
A[j - 1] = t;
swapcount++;
}
j++;
}
i++;
}
What's the running time of this algorithm? Well, that depends on whether or not we run into a situation where swapcount is zero, and if so on when that happens. The only thing we know for sure is that it can't be worse that Θ(n^2), because that's what we get without the swapcount. When we can't say "the running time T(n) grows like f(n)", but we can say "the running time T(n) certainly grows no faster than f(n), though it might actually grow more slowly", we write that "T(n) = O(f(n))". In this case we say of the running time T(n) of BubbleSortV2.0 that T(n) = O(n^2). So, Θ(n^2) means "grows like n^2", while O(n^2) means "grows no faster (though possibly slower!) than n^2".
Suppose you have an array A of n strings and you've got a string x of length k that you know is in A. You want to find the index of x in A. Keep in mind that when you compare strings s and t using "s == t" or "s != t", a character by character comparison is done. How long will it take to find x's index by starting at the front of A and looking at each successive string until a match is found? Well, that depends on all sorts of things. It's impossible to give an answer like T(n), the running time of the search algorithm, is Theta of something. You don't know how far you'll have to search in the array. You don't know how long each of the strings are. You don't know how many characters you'll have to examine in each string to see if they match x. The only thing you can say for sure is that it can't take longer than examining k characters of every one of the n strings in the array. So, the running time T(n) can't grow faster than n*k, i.e. T(n) = O(n*k).