Although you are welcome to typeset your work nicely (using Microsoft Word
or LaTeX or whatever to get nice logic symbols),
it's probably much easier to write formulas by hand.
When showing that one function is big-Oh of another,
use the definition of big-Oh and find specific constants
c,k satisfying the definition of big-Oh
In class
I used N instead of Rosen's k.
Rosen p.191, #14
(5ed: p.142 #14)
false (λx.x³ ∉ O(λx.x²))true (λx.x³ ∈ O(λx.x³))true (λx.x³ ∈ O(λx.x²+x³))true (λx.x³ ∈ O(λx.x²+x2))true (λx.x³ ∈ O(λx.3x))true (λx.x³ ∈ O(λx.x³/2))
Rosen p.191, #10.
(5ed: p.142 #10)
(This is a proof.)
Show that x³ ∈O(x):
∀x≥1,
x³ ≤ x³·x = x.
Thus, by the definition of big-Oh (with c=1 and N=1)
we have λx.x³ ∈ O(λx.x)
Show that x ∉ x³:
That is,
we show that
∀c,∀N, ∃n>N such that
n ≥ c·n³.
Take any c,N.
Then, let n=max(c,N).
Since n≥c, we also have
n = n·n³ ≥ c·n³
Therefore, no matter what c,N are chosen,
there is a number n such that n≥N, and yet
¬( n < c·n³),
meaning that
λx.n ∉ O(λx.x³)
Rosen p.191, #16.
(5ed: p.142 #16)
(Note that this is a proof.)
f∈O(λn.n)premise∃c,N.∀n>N,
f(n)<c·n.def'n of big-Oh
∀n>max(N,1),
f(n)<c·n·n = c·n²Can multiply the larger side of an inequality by
1 or more, and preserve the inequality.∃c',N'.∀n>N',
f(n) < c·n²Take c'=c, and N'=max(N,1).
f(n) ∈ O(λn.n²)def'n of big-Oh.
Rosen p.191, #18.
(5ed: p.142 #18)
(This is a proof.)
∀n≥1,
1 + 2 + 3 + … + n
≤
n + n + n + … + n
(since we are replace each term by a larger one)
= n·n
= 1·n.
Thus
λn.(
1 + 2 + 3 + … + n
)
∈
O(λn.n),
by definition of big-Oh (with c=1, N=1).
If you see a few other problems in Rosen which catch your eye,
and you'd like to do them for extra credit, you are welcome to
(though you can ask me for how much; extra-credit is harder to earn
point-per-point than regular credit).
If you write your own html, you might be interested in this
page of useful html math (and other) entities