Homework Answers
Algorithm 1 gives the best visual representation of the code.
The given code has 3 nested loops, each running for 'n' iterations . Hence total iterations of the nested loops would be n*n*n.
The code then exits the nested sturcutre and begins another loop which iterates for only n/2 steps.
Hence we can visualize it as another block with iterations=n/2
Hence, algorithm 1 suits the code the best.
Add Answer to:
II. ALGORITHM COMPLEXITY AND ASYMPTOTIC ANALYSIS The below visual representations of iterative looping structures are provided...
1(5 pts): For each code fragment below, give the complexity of the algorithm (O or Θ)....
1(5 pts): For each code fragment below, give the complexity of the algorithm (O or Θ). Give the tightest possible upper bound as the input size variable increases. The input size variable in these questions is exclusively n. Complexity Code public static int recursiveFunction (int n)f f( n <= 0 ) return 0; return recursiveFunction (n - 1) 1; for(int i 0i <n; i+) j=0; for ( int j k=0; i; k < < j++) for (int j; m <...
discrete math (1) (15 pts) Time Complexity Analysis 1) (5 pts) What is the time complexity...
discrete math
(1) (15 pts) Time Complexity Analysis 1) (5 pts) What is the time complexity of the following code segment? Explain your answer; otherwise, you can't get full mark from this question. for(int i=1; i<n; i*=2) { sum-0; sum++; Answer: 2) (5 pts) What is the time complexity of the following code segment? Explain your answer; otherwise, you can't get full mark from this question. for(int j=0; j<n; j++){ for (int k=0; k<n; k++) { for (int =0; i<n;...
Exercise 7.3.5: Worst-case time complexity - mystery algorithm. The algorithm below makes some changes to an...
Exercise 7.3.5: Worst-case time complexity - mystery algorithm. The algorithm below makes some changes to an input sequence of numbers. MysteryAlgorithm Input: a1, a2....,an n, the length of the sequence. p, a number Output: ?? i != 1 j:=n While (i < j) While (i <j and a < p) i:= i + 1 End-while While (i <j and a 2 p) j:=j-1 End-while If (i < j), swap a, and a End-while Return( aj, a2,...,an) (a) Describe in English...
Question One (2 marks): What is the complexity of the given code as a function of the problem size n? Show the (complete) details of your analysis. Note: a [ i] s an array with n elements. for (int i...
Question One (2 marks): What is the complexity of the given code as a function of the problem size n? Show the (complete) details of your analysis. Note: a [ i] s an array with n elements. for (int i- 0; i < n; i++) if (Math.random) > 0.5) if (i%2-0) Insertionsort (a[i]); else Quicksort (a[i]) else for (int j = 0; j < i; j++) for (int k 0: k 〈 i; k++) o (logn)
Question One (2 marks):...
For each C++ function below, give the tightest can asymptotic upper bound that you can determine....
For each C++ function below, give the tightest can asymptotic upper bound that you can determine. (a) void mochalatte(int n) { for (int i = 0: i < n: i++) { count < < "iteration;" < < i < < end1: } } (b) void nanaimobar (int n) { for (int i = 1: i < 2*n: i = 2*i) { count < < "iteration;" < < i < < end1: } } void appletart (int n) { for (int...
Question No.1 [CLO 1][7 marks] 1. Consider the following pseudocode: Algorithm IterativeFunction (a, b) // a...
Question No.1 [CLO 1][7 marks] 1. Consider the following pseudocode: Algorithm IterativeFunction (a, b) // a and b are integers while (a>0) B- a/2 A a-2 end while return b; i. What is the time complexity of the IterativeFunction pseudocode shown above? ii. What is the space complexity of the IterativeFunction pseudocode shown above? 2. What is the time complexity of the following algorithm (Note that n(n+1) 2,2 n(n+1)(2n+1) 2 and ): Provide both T(n) and order, e(f(n)). int A=0;...
When asked to describe an algorithm you are expected to give a clear pseudo-code description of...
When asked to describe an algorithm you are expected to give a
clear pseudo-code description of the algorithm
1. (10 pts) Here is a new sorting algorithm NewSort Suppose the original call made is NewSort(A,0,n-1) where A is an array integers. == void NewSort(int A[], int i, int j){ \\ sorts the subarray Aſi..j] if (j i+1) \\when there are only 2 elements if (A[i] > A[j]) swap(A,i,j) \\swaps A[i] and A[j] else { int k = (j-i+1)/3; NewSort(A,i,j-k); \\...
8. R-4.8 Order the following functions by asymptotic growth rate. 4nlogn + 2n 2^10 2^logn 3n...
8. R-4.8 Order the following functions by asymptotic growth rate. 4nlogn + 2n 2^10 2^logn 3n + 100logn 4n 2^n n^2 + 10n n^3 nlogn 9. R-4.9 Give a big-Oh characterization, in terms of n, of the running time of the example 1 method shown in Code Fragment 4.12. 10. R-4.10 Give a big-Oh characterization, in terms of n, of the running time of the example 2 method shown in Code Fragment 4.12. 11. R-4.11 Give a big-Oh characterization, in...
LANGUAGE IS C++ Lab Ch14 Recursion In this lab, you are provided with startup code which...
LANGUAGE IS C++ Lab Ch14 Recursion In this lab, you are provided with startup code which has six working functions that use looping (for, while, or do loops) to repeat the same set of statements multiple times. You will create six equivalent functions that use recursion instead of looping. Although looping and recursion can be interchanged, for many problems, recursion is easier and more elegant. Like loops, recursion must ALWAYS contain a condition; otherwise, you have an infinite recursion (or...
1(5 pts): For each code fragment below, give the complexity of the algorithm (O or Θ). Give the tightest possible upper bound as the input size variable increases. The input size variable in these questions is exclusively n. Complexity Code public static int recursiveFunction (int n)f f( n <= 0 ) return 0; return recursiveFunction (n - 1) 1; for(int i 0i <n; i+) j=0; for ( int j k=0; i; k < < j++) for (int j; m <...
discrete math
(1) (15 pts) Time Complexity Analysis 1) (5 pts) What is the time complexity of the following code segment? Explain your answer; otherwise, you can't get full mark from this question. for(int i=1; i<n; i*=2) { sum-0; sum++; Answer: 2) (5 pts) What is the time complexity of the following code segment? Explain your answer; otherwise, you can't get full mark from this question. for(int j=0; j<n; j++){ for (int k=0; k<n; k++) { for (int =0; i<n;...
Exercise 7.3.5: Worst-case time complexity - mystery algorithm. The algorithm below makes some changes to an input sequence of numbers. MysteryAlgorithm Input: a1, a2....,an n, the length of the sequence. p, a number Output: ?? i != 1 j:=n While (i < j) While (i <j and a < p) i:= i + 1 End-while While (i <j and a 2 p) j:=j-1 End-while If (i < j), swap a, and a End-while Return( aj, a2,...,an) (a) Describe in English...
Question One (2 marks): What is the complexity of the given code as a function of the problem size n? Show the (complete) details of your analysis. Note: a [ i] s an array with n elements. for (int i- 0; i < n; i++) if (Math.random) > 0.5) if (i%2-0) Insertionsort (a[i]); else Quicksort (a[i]) else for (int j = 0; j < i; j++) for (int k 0: k 〈 i; k++) o (logn)
Question One (2 marks):...
For each C++ function below, give the tightest can asymptotic upper bound that you can determine. (a) void mochalatte(int n) { for (int i = 0: i < n: i++) { count < < "iteration;" < < i < < end1: } } (b) void nanaimobar (int n) { for (int i = 1: i < 2*n: i = 2*i) { count < < "iteration;" < < i < < end1: } } void appletart (int n) { for (int...
Question No.1 [CLO 1][7 marks] 1. Consider the following pseudocode: Algorithm IterativeFunction (a, b) // a and b are integers while (a>0) B- a/2 A a-2 end while return b; i. What is the time complexity of the IterativeFunction pseudocode shown above? ii. What is the space complexity of the IterativeFunction pseudocode shown above? 2. What is the time complexity of the following algorithm (Note that n(n+1) 2,2 n(n+1)(2n+1) 2 and ): Provide both T(n) and order, e(f(n)). int A=0;...
When asked to describe an algorithm you are expected to give a
clear pseudo-code description of the algorithm
1. (10 pts) Here is a new sorting algorithm NewSort Suppose the original call made is NewSort(A,0,n-1) where A is an array integers. == void NewSort(int A[], int i, int j){ \\ sorts the subarray Aſi..j] if (j i+1) \\when there are only 2 elements if (A[i] > A[j]) swap(A,i,j) \\swaps A[i] and A[j] else { int k = (j-i+1)/3; NewSort(A,i,j-k); \\...
Most questions answered within 3 hours.
-
A bond with a par value of $1,000 and a coupon rate of 7.50%
(semiannual coupon)...
asked 6 minutes ago -
explanations of the python. Explain in least 1 to 2 page
about python; this can serve...
asked 7 minutes ago -
QUESTION 10
Which of the following is not true of nonprofit Community Health
Centers that qualify...
asked 17 minutes ago -
For the following reaction, 5.25 grams of
hydrogen sulfide are mixed with excess
oxygen gas. The...
asked 8 minutes ago -
Identify which one of these systems can be considered as
constituting an isolated system.
Two marbles...
asked 11 minutes ago -
10. Explain what is meant by ‘mutually exclusive projects’ and
why it is generally a bad...
asked 22 minutes ago -
Create a powershell script to create a user named: Week10User
(provide whatever other details that may...
asked 16 minutes ago -
Suppose that you wanted to purchase a product and sell it at
your online store. You...
asked 22 minutes ago -
The coefficient of determination R2 in a simple
regression model,
Group of answer choices
a) measures...
asked 23 minutes ago -
Explain why some heterotrophs can be described as both a
primary consumer and a secondary consumer....
asked 27 minutes ago -
Explain the constitutional foundations for federalism.
asked 39 minutes ago -
Perform an internet search and answer the following questions:
Why should a business be concerned with...
asked 48 minutes ago