Discrete Mathematics Answers

Prove that 2^(n+1) > (n + 2) · sin(n) for all positive integers n

(3). If p, q, and r denote the following propositions:

p : 2 < 3.

q : The cube of -1 is -1.

r : The empty set contains one element.

express the following propositions symbolically.

(a) If 2 ≥ 3, then the cube of -1 is -1.

(b) If and only if 2 < 3 or the cube of -1 is not -1 then the empty

set does not contain one element.

(c) The empty set contains one element and, if 2 ≥ 3, then the

cube of -1 is -1.

What is the big-O estimate of the function given in the pseudocode below if the size of the input is n? (a function that takes in a list of numbers as input and returns the biggest number) Justify your answer.

define function(input_list):

for i from range 0 to length(input_list):

min_idx = i

for j from range item+1 to length(input_list):

if input_list[min_idx] > input_list[j]:

min_idx = j

input_list[i], input_list[min_idx] = input_list[min_idx], input_list[i]

return input_list[length(input_list)]

Solve for x if (g ◦ f)(x) = 1. Here, f(x) = (x^log(x) · x²) and g(x) = log(x) + 1.

Find the big−O, big−Ω estimate for x⁷y³+x⁵y⁵+x³y⁷. [Hint: Big-O, big- Ω, and big-Θ notation can be extended to functions in more than one variable. For example, the statement f(x, y) is O(g(x, y)) means that there exist constants C, k₁, and k₂ such that |f(x, y)| ≤ C|g(x, y)| whenever x > k₁ and y > k₂.]

Consider the function f(n) = 35n³+ 2n³log(n) − 2n²log(n²) which represents the complexity of some algorithm.

(a) Find a tight big-O bound of the form g(n) = n^p for the given function f with some natural number p. What are the constants C and k from the big-O definition?

(b) Find a tight big-Ω bound of the form g(n) = n^p for the given function f with some natural number p. What are the constants C and k from the big- Ω definition?

(c) Can we conclude that f is big−Θ (n^p) for some natural number p?

Find a div b and a mod b when:

(a) a = 30303, b = 333

(b) a = −765432, b = 38271

Show that if n | m, where n and m are integers greater than 1, and if a≡b (mod m), where a and b are integers, then a≡b (mod n).