Prove that the function f(x) = (8x + 5) mod 17 is injective on the set f0; 1; 2; 3; : : : ; 15; 16g (10 points).
Is f(x) = (8x + 5) mod 17 invertible on this set? If so, give its inverse function (5 points).
Is f(x) = (8x + 5) mod 18 invertible on this set? If so, give its inverse function (5 points).
True or false - give a mathematical justi cation (10 points):
a) n = O(n2).
b) n(n + 1)(n + 2)
n3
= O(n3).
c) n(n + 1)(n + 2)
n3
= O(n2).
n ln n = O(n2).
n2 = O(n ln n).
1=n = O(1).
1000000n = O(n).
2n = O(3n).
3n = O(2n).
P
n
j)
i=1 i(i + 1)(i + 2) = O(n4).
The ‘double factorial’ is a variant on the factorial function where every other number is multiplied together:
for instance, 9!! = 9 7 5 3 1 = 945, 10!! = 10 8 6 4 2 = 3840. In general, n!! is much smaller than n! (20 points).
{ Argue that n!!=n! goes to 0 as n ! 1, i.e., n! dominates n!! severely. Hint: Be wary of cases.
{ Argue, however, that in the limit for even n, ln(n!!)=(n ln n) is bound from above and below by some constants.
{ Argue that for odd n, ln(n!!)=(n ln n) is bound from above and below by some constants as well. Hint:
Show that n! = n!!(n 1)!!.
{ Conclude therefore that while n! is a lot larger than n!!, we have that ln n!! = (ln n!).
1
