Show that 8𝑛^2 − 5𝑛 + 7 = 𝑂(𝑛^3)
Determine whether each of these functions is bounded by O(n). Say yes or no.
a) 𝑓(𝑛) = 3
b) 𝑓(𝑛) = 𝑛^2 + 𝑛 + 12
c) 𝑓(𝑛) = (𝑛)
d) 𝑓(𝑛) = 17𝑛 + 7
e) 𝑓(𝑛) = 15𝑛 log 𝑛
f) 𝑓(𝑛) = (𝑛/2)
Arrange the following functions in ascending order of growth rate.
𝑓1(𝑛) = 1.5^𝑛 + 50
𝑓2(𝑛) = 𝑛^100 + 𝑛^3 log 𝑛
𝑓3(𝑛) = (log 𝑛)^3
𝑓4(𝑛) = √𝑛 log 𝑛
𝑓5(𝑛) = 10^𝑛
𝑓6(𝑛) = 𝑛^99 + 𝑛^98
𝑓7(𝑛) = (𝑛!)^2
Solve the following recurrences using Master Theorem.
𝑇(𝑛) = 16𝑇 (𝑛/4)+ 𝑛√𝑛
𝑇(𝑛) = 𝑇 (𝑛/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 printCombo(int n)
{
int [] A = new int[n];
printComboR(1, n, A, 0);
}
public static void printComboR(int i, int n, int[] A, int index)
{
}
Show that 8𝑛^2 − 5𝑛 + 7 = 𝑂(𝑛^3)
To show that 8𝑛^2 − 5𝑛 + 7 = 𝑂(𝑛^3), we need to find constants C and k such that for all values of n greater than k, the inequality 8𝑛^2 − 5𝑛 + 7 ≤ C𝑛^3 holds true.
Let's simplify the equation:
8𝑛^2 − 5𝑛 + 7 ≤ C𝑛^3
Rearranging the terms:
8𝑛^2 − 5𝑛 + 7 - C𝑛^3 ≤ 0
Now, let's take the limit as n approaches infinity:
lim(n->∞) (8𝑛^2 − 5𝑛 + 7 - C𝑛^3) ≤ 0
Since the limit is less than or equal to zero, we can conclude that 8𝑛^2 − 5𝑛 + 7 = 𝑂(𝑛^3).
Determine whether each of these functions is bounded by O(n). Say yes or no.
a) 𝑓(𝑛) = 3
Yes, it is bounded by O(n) because it is a constant function.
b) 𝑓(𝑛) = 𝑛^2 + 𝑛 + 12
Yes, it is bounded by O(n) because the highest degree term is n^2, which grows slower than n^3.
c) 𝑓(𝑛) = (𝑛)
Yes, it is bounded by O(n) because it is a linear function.
d) 𝑓(𝑛) = 17𝑛 + 7
Yes, it is bounded by O(n) because it is a linear function.
e) 𝑓(𝑛) = 15𝑛 log 𝑛
Yes, it is bounded by O(n log n) because it grows slower than n^3.
f) 𝑓(𝑛) = (𝑛/2)
Yes, it is bounded by O(n) because it is a linear function.
Arrange the following functions in ascending order of growth rate.
𝑓3(𝑛) = (log 𝑛)^3
𝑓4(𝑛) = √𝑛 log 𝑛
𝑓2(𝑛) = 𝑛^100 + 𝑛^3 log 𝑛
𝑓6(𝑛) = 𝑛^99 + 𝑛^98
𝑓1(𝑛) = 1.5^𝑛 + 50
𝑓7(𝑛) = (𝑛!)^2
𝑓5(𝑛) = 10^𝑛
Solve the following recurrences using Master Theorem.
a) 𝑇(𝑛) = 16𝑇 (𝑛/4)+ 𝑛√𝑛
The recurrence relation can be written as 𝑎=16, 𝑏=4, and 𝑐=1/2.
Since log₄16 = 2, and 𝑐 = 1/2 < log₄16, we apply case 1 of the Master Theorem.
The time complexity of this recurrence relation is Θ(n²√n).
b) 𝑇(𝑛) = 𝑇 (𝑛/5)+ 10
The recurrence relation can be written as 𝑎=1, 𝑏=5, and 𝑐=0.
Since log₅1 = 0, and 𝑐 = 0 = log₅1, we apply case 2 of the Master Theorem.
The time complexity of this recurrence relation is Θ(log n).
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?
No,
once the coordinates are sorted, we need to divide the points into smaller subsets and recursively compute the closest pair of points within each subset. Sorting the coordinates is a preprocessing step that allows us to efficiently divide the points and apply the divide and conquer strategy. After dividing the points and finding the closest pairs within each subset, we need to merge the results and compare distances to find the overall closest pair of points. So, sorting the coordinates alone does not complete the computation of distances.