Unit 23 Answers
1.
- Not a functin. f(0) is
not defined.
- Not a function. f is not single valued.
For example f(1) = 1 and -1.
- It is a function.
2.
- Domain: the set of bit strings.
Range: the set of natural numbers.
- Domain: the set of bit strings. Range: {0, 1, 2, 3, 4, 5, 6, 7}
3. a) and b) are one-to-one.
- Suppose that f(n1)
= f(n2).
Then n1 + 2 = n2 + 2.
Hence n1 = n2.
Hence f in this case is
one-to-one.
- For example f(1) = 3 = f(-2). Hence f is not one-to-one.
- Suppose that f(n1) = f(n2).
Then n13 - 1
= n23 - 1.
Hence n13
= n23.
Since n1n2
> 0, if n13
= n23, then n1
= n2 follows.
Hence f in this case is
one-to-one.
4.
- Yes
- No. For example nothing in Z is mapped to 0 by f.
- No. For example nothing in Z is mapped to 1 by f.
5.
- Yes If f(x1) =
f(x1), then 2x1 + 3
= 2x2 + 3.
Hence x1 = x2.
Hence f is one-to-one.
For any y in R,
x = (y - 3)/2
is
in R and it is mapped to y
by f.
Hence f is onto.
Hence f is a bijection.
- This f is neither one-to-one nor onto.
Hence it is not a bijection.
6.
- For any x in R, if x > 1,
then 10 < 10x.
Hence 10 = O(x).
- For any x in R, if x > 1,
then 3x + 7 < 10x. Hence 3x + 7 = O(x).
- If x2 + x + 1 = O(x), then there exist
positive numbers C and x0 such that
x2 + x + 1 < Cx for all x
> x0.
However, for any C, if x > C - 1,
then x + 1 - C > 0.
Hence if x > max {0, C - 1},
then x(x + 1 - C) > 0.
Hence x2 + (1 - C)x + 1 > 0. That is,
x2 + x + 1 > Cx
if x > max {0, C - 1}.
Hence for any C there is no x0 such that
x2 + x + 1 < Cx for all x
> x0.
Hence x2 + x + 1 is not O(x).
- Since ex > x if x > 0,
5ln x < 5x for all x > 0.
Hence 5ln x = O(x).
7.
x4 + 5x3
+ 3x2 + 4x + 6 <
x4 + 5x4
+ 3x4 + 4x4
+ 6x4 = 19x4
if x > 1
since x4 > x3,
x4 > x.
Hence x4 + 5x3
+ 3x2 + 4x + 6 is
O(x4).