Studio 1: Asymptotic Complexity

• Part A: Exact Execution Counts
• Part B: Practice with Big-$O$
• Part C: Practice with Big-$\Omega$
• Part D: Practice with Big-$\Theta$
• Part E: Some More Interesting Comparisons

Part A: Exact Execution Counts

Before you get started, do a Team$\Rightarrow$Pull on your repo in Eclipse to make sure your copy is up-to-date. You should do this every time you start work, as we will roll out new studios and labs to your repo throughout the semester.

• Open the Java classes in the studio1 package of your studios folder.

Question A1: find an Excel formula that gives the exact number of times ticker.tick() is called, as a function of the input size n, for each of the following programs:

1. ProbA
2. ProbB
3. ProbC
4. ProbD
5. ProbE

For each of these programs, you should first look at its run() function and locate the ticker.tick() call, then try to construct a closed-form expression that describes the number of calls as a function of n. Use the analysis of loop nests as discussed in class to help you.

You might want to use your summation formulas to help derive a closed-form expression.

When you think you've got a correct expression, run the program and open the resulting tick count .csv file in the outputs folder (did you remember to refresh?). The input size n is given in column A, while the number of ticks for that size is in column B.

Enter your expression in cell C2, translating it into an Excel formula. The quantity n is in cell A2; hence, if your formula is (e.g.) $n^2$, you would enter =A2*A2. Once you have your formula in place, cut and paste it into all rows of column C so that you can compare the formula's output to the empirical measurements in column B.

If you would like some help with Excel formulas, read this introduction.

When using summation formulas, be sure to use the versions that are single fractions, rather the ones that are sums of fractions, to avoid errors due to integer truncation.

Your formula's output should exactly match the number of ticks for each $n \geq 1$. If you're not getting the same numbers, check your expression and modify as needed. Ask your TA for help if you need it!

Part B: Practice with Big-$O$

Recall the definition of big-O notation:

We say that a function $f(n) = O(g(n))$ if there exist constants $c > 0$ and $n_0 > 0$ such that

\[ \forall n \geq n_0, f(n) \leq c \cdot g(n) . \]

Question B1: for each statement below, prove that the statement is true by finding constants $c$ and $n_0$ that satisfy the definition of big-O notation.

1. $n = O(n^2)$
2. $1000n = O(n^2)$
3. $n\log n = O((n+1)^2)$

What constitutes a sufficient argument to prove that your choices of $c$ and $n_0$ work? Give a more convincing argument than just plugging in a few values of $n$! If you can't argue algebraically, how could you use derivatives to prove your claim?

Any logs shown, here and for the rest of class, are assumed to be base-2 unless otherwise specified (or unless the base doesn't matter).

Part C: Practice with Big-$\Omega$

The definition of big-$\Omega$ notation is essentially the same as for big-O, except that we replace upper bounds by lower bounds:

We say that a function $f(n) = \Omega(g(n))$ if there exist constants $c > 0$ and $n_0 > 0$ such that

\[ \forall n \geq n_0, f(n) \geq c \cdot g(n) . \]

This is not obviously the "right" definition of big-$\Omega$, because it is not the logical inverse of the definition for big-O. However, it is an eminently practical definition ¹ because it implies that \[ f(n) = \Omega(g(n)) \iff g(n) = O(f(n)). \] (Take a moment to think about how you would prove this claim.) Hence, to prove an $\Omega$ statement like that on the left side, simply interchange $f$ and $g$ and prove the corresponding $O$ statement. For example, to show that $n^2 = \Omega(an + b)$, it is enough to show that $an + b = O(n^2)$.

Question C1: Rewrite each statement below into Big-O form, and then show that the Big-O version is true using the same technique as in Part B.

1. $n^2 = \Omega(5000)$
2. $n = \Omega(an + b)$

Part D: Practice with Big-$\Theta$

Big-$\Theta$ notation describes "well-behaved" functions that can be bounded both from above and from below.

We say that a function $f(n) = \Theta(g(n))$ if $f(n)$ is both $O(g(n))$ and $\Omega(g(n))$.

Note that the two parts of the definition may involve different constants $c$ and $n_0$.

Question D1: For each of the two pairs of functions in Question C1, is the left-hand function $\Theta$ of the right-hand function? Prove or disprove.

How do you prove that a function is not big-O of another function? Consider a proof by contradiction -- pick $c$ and $n_0$, and...

Part E: Some More Interesting Comparisons

Question E1: For each of the following pairs of functions, $f$ and $g$, which grows faster as $n$ gets large?

State your answer using $O$, $\Omega$, or $\Theta$ notation and prove your answer correct. You may wish to use data generation in Excel to develop some intuition first.

Because you'll be dealing with logs, you might need to use derivatives or some fun math facts, such as the fact that \[ \log_a x = \frac{\log x}{\log a} . \]

Question E2: Recall the Doubling implementation of array growth in Studio 0. The number of ticks needed to add $n$ elements to the array grew like this:

Argue that the number of ticks is in fact $\Theta(n)$.

For piecewise-linear functions such as this, what do you actually need to prove to establish a big-O bound?