Cartesian product A=(2,4}B={2,3,5} AXB={(2,2,(2,3),(2,5,(4,2)2(4,3),(4,5)} AXB=*B Generalizes to more than two sets AⅩBX..XZ
Cartesian Product A = { 2, 4 } B = { 2, 3, 5 } A X B = { (2, 2), (2, 3), (2, 5), ( 4, 2), (4, 3), (4, 5) } |A X B| = |A|*|B| Generalizes to more than two sets A X B X … X Z
Examples What is:{1,2,3}×{a.b}=(1,a,2(1,b),(2,a),(2,b).(3,a),(3,b) .True or false:((1 a),(3,b)(1, 2, 3) xfa, bj true .True or false: (1, 2, 3c(1, 2, 3x a, b)
Examples: •What is: {1, 2 , 3} {a,b} = •True or false: {(1,a), (3,b)} {1, 2 , 3} {a,b} •True or false: {1,2,3} {1, 2 , 3} {a,b} true false {(1,a), (1,b), (2,a), (2,b), (3,a), (3,b)}
FUNCTIONS Given two sets a and b. a function from a into b associates with each a in a at most one element b of B domain range 4 A f(1)=a a 2 5 f: A->B
FUNCTIONS domain 1 2 3 a b c range f : A -> B A B f(1) = a 4 5 Given two sets A and B, a function from A into B associates with each a in A at most one element b of B
fa->B ifa= domain then f is a total function otherwise f is a partial function 1234 BCA f:A→> B is a bijection o fis total o for all a and a' in A, al=a implies f(a)=f(a) o for all b in b, there is a in a with f(a=b
f : A -> B ◼ If A = domain then f is a total function otherwise f is a partial function ◼ f : A -> B is a bijection f is total for all a and a’ in A, a!=a’ implies f(a)!=f(a’) for all b in B, there is a in A with f(a)=b
Big o notation Given two total function f: N->N o we write f(n)=o(g(n)), if there are positive integers c and d such that, for all n> d f(n)<cg(n) o we write f(n=Q(g(n), if there are positive integers c and d such that, for all n> d, (n)>g(n) If f(n=o(g(n)) and f(n=Q2(gn)), then we write f(n)=0(g(n) Whenever f(n=O(g(n), then g(n) is an upper bound for f(n)and whenever f(n)=Q2(g(n)),g(n) is a lower bound for fn) The big-O notation compares the rate of growth of functions rather than their values, so when f(n)=0(g(n)), f() and g(n) have the same rates of growth, but can be very differentin theirvalues f(n)=9(g(n)<→>g(n)=O(f(n)
Big O Notation ◼ Given two total function f,g:N->N, we write f(n)=O(g(n)), if there are positive integers c and d such that, for all n≥ d, f(n) ≤cg(n); we write f(n)=Ω (g(n)), if there are positive integers c and d such that, for all n≥ d, cf(n) ≥ g(n). ◼ If f(n)=O(g(n)) and f(n)=Ω (g(n)), then we write f(n)=θ(g(n)). ◼ Whenever f(n)=O(g(n)), then g(n) is an upper bound for f(n) and whenever f(n)=Ω (g(n)), g(n) is a lower bound for f(n). ◼ The big-O notation compares the rate of growth of functions rather than their values, so when f(n)=θ (g(n)), f(n) and g(n) have the same rates of growth, but can be very different in their values. ◼ f(n)=Ω (g(n)) <=> g(n)=O(f(n))