solve computer science 2 question

Show that 8𝑛 − 5𝑛 + 7 = 𝑂(𝑛 )

Determine whether each of these functions is bounded by O(n). Say yes or no.

𝑓(𝑛) = 3a) 𝑓(𝑛) = 𝑛 + 𝑛 + 12b) 𝑓(𝑛) = ⌊𝑛⌋c) 𝑓(𝑛) = 17𝑛 + 7d) 𝑓(𝑛) = 15𝑛 log 𝑛e)

𝑓(𝑛) = 𝑛

2 f)

Exam 1 Review Friday, January 26, 2024 7:14 AM

Arrange the following functions in ascending order of growth rate.

Solve the following recurrences using Master Theorem.

𝑇(𝑛) = 16𝑇 𝑛

4 + 𝑛√𝑛

𝑓 (𝑛) = 1.5 + 50 𝑓 (𝑛) = 𝑛 + 𝑛 log 𝑛 𝑓 (𝑛) = (log 𝑛) 𝑓 (𝑛) = √𝑛 log 𝑛 𝑓 (𝑛) = 10 𝑓 (𝑛) = 𝑛 + 𝑛 𝑓 (𝑛) = (𝑛!)

𝑇(𝑛) = 𝑇 𝑛

5 + 10

In the divide and conquer closest pair of points, we sorted the coordinates (x or y). Once sorted, are we ready to start computing distances?

Given a positive number 𝑛, find all combinations of 2𝑛 elements such that every element from 1 to 𝑛 appears exactly twice and the distance between its two appearances is equal to the value of the element. Complete the following a backtracking algorithm (findAllComboR) in Java. Example: n = 3 Output: 3 1 2 1 3 2

2 3 1 2 1 3

n = 4 Output: 4 1 3 1 2 4 3 2

2 3 4 2 1 3 1 4

public static void findAllCombo(int n) {

int[] arr = new int[2*n]; Arrays.fill(arr, -1); findAllComboR(arr, 1, n);

}

public static void findAllComboR(int[] arr, int x, int n) {

}

Complete the backtracking algorithm in Java (printComboR) to print all possible combinations of numbers 1 and 𝑛 having the sum 𝑛. Assume 𝑛 is a positive integer.

Example: n = 5 [5] [1,4] [2,3]

public static void printComboR(int i, int n, int[] A, int index) {

}

public static void printCombo(int n) {

int [] A = new int[n]; printComboR(1, n, A, 0);

}