## Asymptotic Complexity Part 1

Authors:
• Jeremy Buhler
• Ron Cytron

Abstract: You have used ticker.tick() to keep track of operation counts. In this assignment you will first find exact formulas for the number of operations performed at a specific point in a program, in terms of n, a parameter for the programs' executions. Then you will reason about some expressions and show that they are, or are not bounded from above by another function.
What you should learn through this assignment:
• You can analyze code to derive precise expressions for operation counts.
• You can use excel to compare the expressions you devise with counts that are actually measured in programs.
• You can prove that for some functions f(n) and g(n), f(n) is O(g(n)).
• You are able to apply two other notions of bounding function behavior, Big-Ω and Big-Θ, because they follow from what you have learned about Big-O.

Throughout this assignment you will be supplying answers to questions posed here. Such questions appear in boxes like this one.

You are in a group, but only one of you needs to open and complete the text file. When you demo, you can specify whose repository contains the write up, and we will propagate code and write ups to the other group members.

Ideally, the write up is on your shared monitor if you have one.

So, one of you, please find and open the studio1.txt file in the studiowriteups folder.

## A. Exact Execution Counts

• Here, and always, do a TeamPull to make sure your copy of your repository is up-to-date.
• For this part, you may find the following pages of summation formulas helpful:
• summation formulas
• wiki page, but be sure to use the single fraction version of the summations. The others can lead to integer truncation and give you the wrong answer.
Find the Java classes in the studio1 package of your studios folder.

The FromLecture and FromLastStudio classes are the ones I did in lecture. It is your task to do

• ProbA
• ProbB
• ProbC
• ProbD
• ProbE

For each of those, perform the following steps:

• Look at the code in the run() method and find the ticker.tick() call.
• Spend a few minutes thinking about a formula that represents how often that line executes, in terms of n.
• Run the program.
• Refresh the outputs folder.
• Find and open the corresponding .csv file.
• In the third column, try your formula and see if it corresponds to the actual number of measured ticks.

In the first row of measured ticks, the value of n is known as A2 in an excel formula.

Thus, n2 is entered as =A2*A2.

Be sure to drag your cell sufficiently far down the sheet so you can make sure your formula's computed values correspond exactly to the measured ones.
• Modify your formula as necessary, getting help from the TAs, until the modeled ticks exactly correspond to the measured ticks.
In the studio1.text file, record the successful formulas as answers to the questions posed there.

## B. Big O

Recall from lecture our definition of Big O:

• For each statement below, work together to show that the statement is true.
• Any logs shown are assumed to be base-2 unless otherwise specified.
• As you saw in lecture, find a c and n0 that make the statement true:
• Show your work to a TA as you go.
Answer in the studio write-up, in Part B:

1. n = O(n2)

2. 1000n = O(n2)

3. n log n = O((n+1)2)

## C. Big Ω

Sometimes we would like to show that f(n) is bounded from below instead of above. In that case, we use Ω(…) in place of O(…).

Our text gives a separate definition of Ω(…), but thanks to Knuth we can simply swap expressions and use Big O to show the Ω(…) holds.

For example, in lecture we saw (on a graph, not in a proof) that an + b = O(n2). At some point, some multiple of n2 becomes no less than an+b, no matter the value of a or b.

We can state this in terms of Ω as follows:

n2 = Ω(an+b)
which says there is some multiple c of an+b and some n0 such that for all n ≥ n0 n2 ≥ c (an+b)
To make this work, we do have to find c>0, but remember that c can be less than 1.

But wait!

If we already know how to do Big-O proofs, then we can simply swap the left hand side for Ω's input, and then do a Big-O proof:

 Instead of showing n2 = Ω(an+b) We can show an+b = O(n2)

For each statement below, rewrite it into Big-O form and then show that the Big-O version is true (like you did in part B:

1. n2 = Ω(5000)

2. an + b = Ω(n)

## D. Big Θ

If for two functions f(n) and g(n) we can show that both of the following hold:
• f(n) = O(g(n))
• f(n) = Ω(g(n))

then we can say f(n) = Θ(g(n))

A common point of confusion concerns c, the multiplier used on the bounding function. While there must be some positive values for c that make each of the two bulleted statements true, they are almost certainly not the same value of c.

For example, I can show 100 = Θ(1000) as follows:
• First, show that 100 = O(1000).
• Here I can choose c=1
• Because 100 ≤ 1×1000
• I can choose n0=1, because the choice doesn't matter
• Second, show that 100 = Ω(1000).
• But we do this by showing 1000 = O(100)
• Choosing c=1 won't work.
• But I can chose c=50
• Because 1000 ≤ 50×100
• As above, the choice for n0 doesn't really matter so I will pick n0=1
Go back and look at each of the Big-O and Big-Ω statements you were asked to show for Parts B and C.

For one of them, you can make a Big-Θ proof. Which one?

Provide the proof.

## E. If you make it this far …

• For each of the following pairs of functions, f and g, which grows faster as n gets large?

You can use excel to generate data for the functions and develop intuition.

Function f Function g
nn n!
1.01n n1000
n log n n1.5

• Recall the ticks plot associated with doubling an array when you need more space from Studio 0:

Prove that the ticks are Θ(n).

• If there is a file for you to complete in studiowriteups, please respond to the questions and supply any requested information.
• You must commit and push all of your work to your repository. It's best to do this from the top-most level of your repository, which bears your name and student ID.