370 J;;I. Theory of computer Science
7. The truth value of f(x, Y, .::) = (x v -,y) 1\ (-, X V y) 1\ .:: is T if x, y. z
have the truth values
(a) T. T. T
(b) F. F. F
(c) T, F. F
(d) F. T. F
State whether the following Statements 8-15 are true or false.
8. If the truth values of x, y. .:: are T. F. F respectively. then the truth value
of f(x. y, .::) = x 1\ -,(v v .::) is T.
9. The complexity of a k-tape TM and an equivalent standard TM are the
same.
10. If the time complexity of a standard TM is polynomial, then the time
complexity of an equivalent k-tape TM is exponential.
11. If the time complexity of a standard TM is polynomial. then the time
complexity of an equivalent 1'.TTM is exponential.
12. fix. y, .::) = (x v y v :::) 1\ (-, X 1\ -, Y 1\ -,.::) is satisfiable.
13. f(x. Y . .::) = (x v y) 1\ (-,.Y 1\ -, v) is satisfiable.
14. If f and g are satisfiable expressions, then f v g is satisfiable.
15. If f and g are satisfiable expressions. then f 1\ g is satisfiable.
EXERCISES
12.1 If fen) = O(ll) and g(n) = O(lh then show that fen) + g(n) = O(nt)
where t = max{k, l} and f(n)g(n) = O(n
k
+
I ).
12.2 Evaluate the growth rates of (i) fin) = 2n
2 . (ii) g(n) = 1On
2 + 7n log n +
log 11. (iii) hen) = n 2 10g n + 211 log n + 7n + 3 and compare them.
12.3 Use the O-notation to estimate (i) the sum of squares of first n natural
numbers. (ii) the sum of cubes of first n natural numbers, (iii) the sum
of the first n terms of a geometric progression whose first term is a and
the common ratio is r, and (iv) the sum of the first n terms of the
arithmetic progression whose first term is a and the common difference
is d.
12.4 Show that fen) = 311 2 log2 11 + 411 log3 11 + 5 log2log211 + log 11 + 100
dominates 11 2 but is dominated by 11'.
12.5 Find the gcd (294. 15) using the Euclid's algoritr,m.
12.6 Show that there are five truth assignments for (P, Q, R) satisfying
p v (-, P /\ -, Q 1\ R).