State the definition of an algorithm and define specific

Question

1. State the definition of an algorithm and define specific attributes that must be possessed by an algorithm.

2. Mathematically prove or disprove: log₆x = ½log₃x

3. Prove that (n + 1)² ∈ 0(n²) by giving the smallest value of n₀ and corresponding constant c in the definition of 0-notation.

4. What, if anything, is wrong with the following statement?

Since n = O(n), 2n = O(n),..., we have _k=1∑ⁿkn = _k=1∑ⁿO(n) = O(n²)

5. Which of the following are true and which are false? If true, provide the smallest value of no and corresponding constants c₁ and c₂ satisfying the definition of Θ-notation.

a. 2/n + 4/n² ∈ Θ(1/n²)

b. n log₁₀n ∈ Θ (n log₂n)

c. log₂n^½ ∈ Θ (log₂n)

6. Give asymptotically tight big-O bounds for T(n) in each of the following recurrences. Justify your solution by naming the master method case, by iterating the recurrence or by using the substitution method.

a. T(n) = T(n - 2) + 1

b. T(n) = 2T(n/2) + n lg² n

c. T(n) = 9T(n/4) + n²

d. T(n) = 3T(n/2) + n

e. T(n) = T(n/2 + n^0.5) + n

7. Consider a set S of n ≥ 2 distinct numbers all greater than zero in unsorted order. For each of the problems below:

• Give an algorithm to determine two distinct numbers x and y in the set S that satisfy the condition(s) of the problem.
• Your algorithm must be specified using pseudocode in the style of the text.
• You must justify that your algorithm has the requested run time.

a. In O(n Ig n) time, determine x, y ∈ S such that x ≠ y and |x-y| ≤ |w-z| for all w, z ∈ S such that w ≠ z.

b. In O(n) time, determine x, y ∈ S such that |x - y| ≥ |w-z| for all w, z ∈ S for all w, z ∈ S such that w ≠ z.