CSE 247 Module 1: Asymptotic Complexity

Studio

Asymptotic Complexity Part 1

Authors:
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:
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

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

For each of those, perform the following steps:

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:

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:

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:
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 …

Consider the following problems, entering comments about them at the bottom of your studio write-up:

Submitting your work (read carefully)


Last modified 14:54:19 CDT 31 October 2016
When you done with this studio, you must be cleared by the TA to receive credit.

This demo box is for studio 1
Last name WUSTL Key Propagate?
(NOT your numeric ID) Do not propagate
e.g. Smith j.smith
1 Copy from 1 to all others
2 Copy from 2 to all others
3 Copy from 3 to all others
4 Copy from 4 to all others
TA: Password: