Determine the running time of the following algorithms. Write summations to represent loops and simplify. Justify...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
Determine the running time of the following algorithms. Write summations to represent loops and simplify. Justify your solution. When using upper and lower bounds, be sure to justify both the upper bound and lower bound and check that the bounds differ by only a constant factor. 4. Func4(n) S 1 0; for i 4 to 4n do 2 3 for j = 1 to 15i do 4 for k 3 to 10 do 5 ST s + i j + k; 6 end 7 end 8 end 9 return (s); 5. Func5(n) 1 s 0; 2 4 2345 for i for j 4 to n do - 6 to 3i|log2 il do s s + i j; 5 end 6 end 7 return (s); 6. Func6(n) 1 S 0; 2 3 for in to 4n do for j 1 to i do 4 ssij; 5 end 6 end 7 return (s); Determine the running time of the following algorithms. Write summations to represent loops and simplify. Justify your solution. When using upper and lower bounds, be sure to justify both the upper bound and lower bound and check that the bounds differ by only a constant factor. 4. Func4(n) S 1 0; for i 4 to 4n do 2 3 for j = 1 to 15i do 4 for k 3 to 10 do 5 ST s + i j + k; 6 end 7 end 8 end 9 return (s); 5. Func5(n) 1 s 0; 2 4 2345 for i for j 4 to n do - 6 to 3i|log2 il do s s + i j; 5 end 6 end 7 return (s); 6. Func6(n) 1 S 0; 2 3 for in to 4n do for j 1 to i do 4 ssij; 5 end 6 end 7 return (s);
Expert Answer:
Related Book For
Data Structures and Algorithm Analysis in Java
ISBN: 978-0132576277
3rd edition
Authors: Mark A. Weiss
Posted Date:
Students also viewed these programming questions
-
QUIZ... Let D be a poset and let f : D D be a monotone function. (i) Give the definition of the least pre-fixed point, fix (f), of f. Show that fix (f) is a fixed point of f. [5 marks] (ii) Show that...
-
For monotone functions f, f0: P Q between posets (P, vP ) and (Q, vQ), let f v f(i) Prove that the binary relation v is a partial order. [3 marks] (ii) For monotone functions between posets p : P 0...
-
Use the information in Exercise 2-16 to prepare an August 31 balance sheet for Help Today. Hint: Compute the ownerscapital account balance as of August 31. Data from Exercise 2-16 Carmen Camry...
-
On September 30, 2014, Gargiola Inc. issued $4 million of 10-year, 8%, convertible bonds for $4.6 million. The bonds pay interest on March 31 and September 30 and mature on September 30, 2024. Each...
-
Under normal atmospheric conditions, the surface of the Earth is negatively charged. What is the direction of the electric field near the Earths surface?
-
Refer to the information in QS 13-4. Use that information for Tide Corporation to determine the 2016 and 2017 common-size percents for cost of goods sold using net sales as the base. Data From QS...
-
Gregs Bicycle Shop has the following transactions related to its top-selling Mongoose mountain bike for the month of March 2015: Required: 1. Calculate ending inventory and cost of goods sold at...
-
Given a public good with supply given by P = 2 + Q, and 4 consumers, each with demand of P = 15.5 - Q, find the optimal aggregate CS (Answer 1) and PS (Answer 2). Blank # 1 Blank # 2 A
-
A share is currently selling for sh. 120. There are two possible prices of the share after one year: Sh. 132 or Sh. 105. Assume that the risk-free rate of return is 9 percent per annum. What is the...
-
Which of the dependence measures discussed in the examples satisfy Axiom (i)? Justify the answers with proofs or counterexamples.
-
A patient sues a pharmacy for malpractice, alleging that a medication prescribed by a physician and dispensed by the pharmacy caused the patient harm. The attorney for the pharmacy made a motion for...
-
Bill is the pharmacy owner and PIC at Bills Pharmacy. The state Bills pharmacy is in has a freedom of choice law regarding third-party plans. You have been a long-time customer of Bills and you...
-
Using your state laws and rules, how does your state regulate LTCFs regarding pharmacies and/or pharmacists? Are these laws and regulations under the states pharmacy practice act or in another set of...
-
Billy is a pharmacist at Main Street Pharmacy and Sue the PIC. A routine inspection by a state pharmacy board inspector revealed that Billy had been refilling certain patients prescriptions without...
-
The 7-Eleven chain of convenience stores in Japan reorganized its system for supplying its stores with food. This led to a sharp reduction in the number of trucks the company had to use, while...
-
The following information is for Montreal Gloves Inc. for the year 2020: Manufacturing costs Number of gloves manufactured Beginning inventory $ 3,016,700 311,000 pairs 0 pairs Sales in 2020 were...
-
Merge the two skew heaps in Figure 6.58. 11 12 17 10 (11 18 18 15 (31 21
-
The input is an N by N matrix of numbers that is already in memory. Each individual row is increasing from left to right. Each individual column is increasing from top to bottom. Give an O(N)...
-
Show how the recursive multiplication algorithm computes XY, where X = 1234 and Y = 4321. Include all recursive computations.
-
A first-order dynamic system is modeled as \[\dot{y}+3 y=f(t), y(0)=1\] Assuming the input \(f(t)\) is a step function with magnitude 0.8 , find \(y_{s s}\).
-
The nonlinear state-variable equations for a dynamic system are derived as Plot \(x_{1}(t)\) versus \(0 \leq t \leq 10\) by a. Using the RK4 method. b. Simulating the Simulink model of the system. [...
-
Draw the Bode plot and identify the corner frequency, as well as the asymptotic approximations of magnitude for low-frequency and high-frequency ranges. \(G(s)=\frac{4}{3 s+\frac{2}{3}}\)
Study smarter with the SolutionInn App