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.
Find the Java classes in the studio1 package of your studios folder.
- Here, and always, do a Team…Pull 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.
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:
If you would like some help with excel formulas, click here.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.In the first row of measured ticks, the value of n is known as A2 in an excel formula.
Thus, n^{2} is entered as =A2*A2.
In the studio1.text file, record the successful formulas as answers to the questions posed there.
Answer in the studio write-up, in Part B:1. n = O(n^{2})
2. 1000n = O(n^{2})
3. n log n = O((n+1)^{2})
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(n^{2}). At some point, some multiple of n^{2} becomes no less than an+b, no matter the value of a or b.
We can state this in terms of Ω as follows:
n^{2} = Ω(an+b)which says there is some multiple c of an+b and some n_{0} such that for all n ≥ n_{0} n^{2} ≥ 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 n^{2} = Ω(an+b) We can show an+b
= O(n^{2})
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. n^{2} = Ω(5000)
2. an + b = Ω(n)
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 n_{0}=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 n_{0} doesn't really matter so I will pick n_{0}=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.
You can use excel to generate data for the functions and develop intuition.
State your answer in terms of O(…), Ω(…), or Θ(…), and provide an explanation for your answers.
Function f | Function g |
---|---|
n^{n} | n! |
1.01^{n} | n^{1000} |
n log n | n^{1.5} |
Prove that the ticks are Θ(n).
When you done with this studio, you must be cleared by the TA to receive credit.
- Commit all your work to your repository
- Fill in the form below with the relevant information
- Have a TA check your work
- The TA should check your work and then fill in his or her name
- Click OK while the TA watches
- If you request propagation, it does not happen immediately, but should be posted in the next day or so
This demo box is for studio 1