Discrete Mathematics Answers

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).

Find, showing all working, a formula for the n-th term tn of the sequence (tn) defined by

t1 = 5; tn = -7tn-1 /3, n >= 2.

III. Determine the truth value of each of these statements if the domain consists of all integers. State your reason. 1. ∀𝑥, (𝑥 2 > 𝑥) 2. ∃𝑦, (𝑦 < 𝑦 2 − 1) 3. ∀𝑦, (𝑦 2 ≠ 𝑦) 4. ∃𝑥, 𝑦, (4𝑥 > 5𝑦) where 𝑥 < 𝑦 5. ∀𝑥, 𝑦, (𝑥𝑦 > 0) where 𝑥 = y

(4). Write the converse, inverse, and contrapositive of the statement “If

5 is an odd number, then it is a prime number.”

(5). Draw a truth table and determine for what truth values of p and q

the proposition ∼ q ∨ p is false.

(6). Construct truth tables for

(a) (∼ p ∨ q) =⇒ r

(b) p ∧ (q ∨ r) ⇐⇒ ∼ q