Description
Problem 1. (20 points)
For each of the following functions, determine whether that function is of the same order as n
2
either by
finding witnesses or showing that sufficient witnesses do not exist:
1. 13n + 12
13n is O(n)
2. n
2 + 1000n log n
3. 3n
4. 3n
2 + n − 5
5.
n
3 + 2n
2 − n + 3
4n
Solution.
1. 13n + 12
Is 13n + 12 O(n
2
)? Is 13n + 12 Ω(n
2
)?
13n + 12 ≤ C(n
2
) 13n + 12 ≥ C(n
2
)
13n + 12 ≤ C(13n
2 + 12) 13n + 12 6≥ n
2
for all values of C and k
13n + 12 ≤ 25n
2 C = 25; k ≥ 0
13n + 12 is O(n
2
) with C = 25 and k ≥ 0 as witnesses but 13n + 12 is not Ω(n
2
) because there
are no witnesses that satisify that. Thus 13n + 12 is not Θ(n
2
) and therfore 13n + 12 is not of the
same order as n
2
2. n
2 + 1000n log n
Is n
2 + 1000n log n O(n
2
)? Is n
2 + 1000n log n Ω(n
2
)?
n
2 + 1000n log n ≤ C(n
2
) n
2 + 1000n log n ≥ C(n
2
)
n
2 + 1000n log n ≤ C(n
2 + 1000n
2
) n
2 + 1000n log n ≥ C(
1
2
n
2 + 0n
2
)
n
2 + 1000n log n ≤ 1001n
2 C = 1001; k ≥ 1 n
2 + 1000n log n ≥
1
2
n
2 C =
1
2
; k ≥ 1
n
2 + 1000n log n is O(n
2
) wtih C = 1001 and k ≥ 1 as witnesses and n
2 + 1000n log n is Ω(n
2
)
with C =
1
2
and k ≥ 1 as witnesses. Thus n
2 + 1000n log n is Θ(n
2
) and therfore n
2 + 1000n log n is
of the same order as n
2
1
3. 3n
Is 3n O(n
2
)? Is 3n Ω(n
2
)?
3
n ≤ C(n
2
) 3n ≥ C(n
2
)
3
n 6≤ n
2
for all values of C ≥ 0 and k ≥ 0 3n ≥ n
2 C = 1; k ≥ 0
3
n is not O(n
2
) because there are no witnesses that satisify that but 3n is Ω(n
2
) with C = 1 and
k ≥ 0 as witnesses. Thus 3n is not Θ(n
2
) and therfore 3n is not of the same order as n
2
4. 3n
2 + n − 5
Is 3n
2 + n − 5 O(n
2
)? Is 3n
2 + n − 5 Ω(n
2
)?
3n
2 + n − 5 ≤ C(n
2
) 3n
2 + n − 5 ≥ C(n
2
)
3n
2 + n − 5 ≤ C(3n
2 + n
2 + n
2
) 3n
2 + n − 5 ≥ C(
1
2
n
2 + 0n
2 + 0n
2
)
3n
2 + n − 5 ≤ 5n
2 C = 5; k ≥ 1 3n
2 + n − 5 ≥
1
2
n
2 C =
1
2
; k ≥ 1
3n
2 + n − 5 is O(n
2
) wtih C = 5 and k ≥ 1 as witnesses and 3n
2 + n − 5 is Ω(n
2
) with C =
1
2
and
k ≥ 1 as witnesses. Thus 3n
2 + n − 5 is Θ(n
2
) and therfore 3n
2 + n − 5 is of the same order as n
2
5.
n
3 + 2n
2 − n + 3
4n
Is n
3+2n
2−n+3
4n O(n
2
)? Is n
3+2n
2−n+3
4n Ω(n
2
)?
n
3+2n
2−n+3
4n ≤ C(n
2
)
n
3+2n
2−n+3
4n ≥ C(n
2
)
n
2
4
+
n
2
+
3
4n
≤ C(n
2 + n
2 + n
2
)
n
2
4
+
n
2
+
3
4n
≥ C(
1
5
n
2 + 0n
2 + 0n
2
)
n
2
4
+
n
2
+
3
4n
≤ 3n
2 C = 3; k ≥ 1
n
2
4
+
n
2
+
3
4n
≥
1
5
n
2 C =
1
5
; k ≥ 1
n
3+2n
2−n+3
4n
is O(n
2
) wtih C = 3 and k ≥ 1 as witnesses and n
3+2n
2−n+3
4n
is Ω(n
2
) with C =
1
5
and
k ≥ 1 as witnesses. Thus n
3+2n
2−n+3
4n
is Θ(n
2
) and therfore n
3+2n
2−n+3
4n
is of the same order as n
2
2
Problem 2. (20 points)
Do Supplementary Exercise 29 of Chapter 3 (page 234).
a) Use pseudocode to specify a brute-force algorithm that determines when given as input a sequence of
n positive integers whether there are two distinct terms of the sequence that have as sum a third term. The
algorithm should loop through all triples of terms of the sequence, checking whether the sum of the first two
terms equals the third. b) Give a big-O estimate for the complexity of the bruteforce algorithm from part
(a).
Solution.
procedure brute-force( a1, a2, a3, …, an)
for i = 1 to n O(n)
for j = i + 1 to n O(n)
for k = 1 to n O(n)
if ai + aj = ak then O(1)
return true
else
return false
The complexity for the algorithm is O(n
3
)
3
Problem 3. (20 points)
Do Exercise 31 of Chapter 1.1 (page 15).
Solution.
a)
p ¬ p p ∧ ¬ p
0 1 0
1 0 0
b)
p ¬ p p ∨ ¬ p
0 1 1
1 0 1
c)
p q (p ∨¬q) → q
1 1 1
1 0 0
0 1 1
0 0 0
d)
p q (p ∨ ¬q) → (p ∧ q)
1 1 1
1 0 0
0 1 0
0 0 1
e)
p q (p → q) ↔ (¬p → ¬ q)
1 1 1
1 0 1
0 1 1
0 0 1
f)
p q (p → q) → (q → p)
1 1 1
1 0 1
0 1 0
0 0 1
4
Problem 4. (20 points)
Do Exercises 19, 21, and 23 of Chapter 1.2 (page 23).
Solution.
19) A is a knight and B is a knave
21) A is a knight and B is a knight
23) A is a knave and B is a knight
5
Problem 5. (20 points)
Do Exercises 50 and 51 of Chapter 1.3 (page 36).
Solution. 50)
a)
p p ¬ p p ↓ p
1 1 0 0
1 1 0 0
0 0 1 1
0 0 1 1
¬ p and p ↓ p have the same truth values
b)
p q p ↓ q (p ↓ q) ↓ (p ↓ q) p ∨ q
1 1 0 1 1
1 0 0 1 1
0 1 0 1 1
0 0 1 0 0
(p ↓ q) ↓ (p ↓ q) and p or q have the same truth values.
c) p ↓ q is the same as ¬(p or q). Also, the logical operators ¬ and or can be used to express any
logical expression, ↓ is logically complete.
51)
p q p → q p ↓ q (p ↓ p) ↓ q ((p ↓ p) ↓ q) ↓ ((p ↓ p) ↓ q)
1 1 1 0 0 1
1 0 0 0 1 0
0 1 1 1 0 0
0 0 1 1 0 0
Thus ((p ↓ p) ↓ q) ↓ ((p ↓ p) ↓ q) is the same as p → q
6
Aggie Honor Statement: On my honor as an Aggie, I have neither given nor received any unauthorized
aid on any portion of the academic work included in this assignment.
Checklist:
1. Did you abide by the Aggie Honor Code?
2. Did you solve all problems and start a new page for each?
3. Did you submit the PDF to eCampus?
7
Powered by TCPDF (www.tcpdf.org)
