COT5407 Fall 2006 Quiz #1Instructor: Tao LiSeptember 7th, 2006Student ID: Name:1. Let R be the binary relation over the set of real number, defined by(A, B) ∈ R ⇐⇒ A is a proper subset of B.For each of the following statements below, answer whether it is true or false.(a) R is reflexive.(b) R is transitive.(c) R is symmetric.2. For each of the following statements below, answer which one of {O, o, Ω, ω, Θ} is the most appro-priate to be put in place for X.(a) 22n∈ X((22)n).(b) lg(n2) ∈ X((lg n)2).(c) 23 lg n∈ X(n3).(d) (√2)√n∈ X(n).1. (a) R is not reflexive because no set can be a proper subset of itself.(b) R is transitive because if X is a proper subset of Y and Y is a proper subset of Z then X is aproper subset of Z.(c) R is not symmetric because if X is a proper subset of Y then Y cannot be a proper subset of X.2. (a) Since (22)n= 22nand 2n∈ ω(2n), 22n∈ ω((22)n).(b) Since lg(n2) = 2 lg n, lg(n2) ∈ o((lg n)2).(c) Since 23 lg n= n3, 23 lg n∈ Θ(n3).(d) Since (√2)√n= 2√n/2and n = 2lg n, (√2)√n∈
View Full Document
Unlocking...