Can you help me with this: In Chapter 4 of Data Structures and Abstractions with

Question

Can you help me with this:

In Chapter 4 of Data Structures and Abstractions with Java (Carrano & Henry, 2015, p. 148-149), help me with the following:

Exercise #14

Exercise #16

Exercise #18

For each exercise, show your work and all of the steps taken to determine the Big-Oh for each problem. Submit all work in a Word document please.

Antonio's Kindle for PC (Wine)- Data Structures and Abstractions with Java Eile ew Go Iools Help Library 4Eacko r Poge 49898 184% v Exercises 149 16. Consider two programs, A and B. Program A requires 1000 × n2 operations and Program B requires 2n operations. For which values of n will Program A execute faster than Program B? 17. Consider four programs-A, B, C, and D-that have the following performances: A: O(log n) B: O(n) C: 0() D: O(2" If each program requires 10 seconds to solve a problem of size 1000, estimate the time required by each program for a problem of size 2000 18. Suppose that you have a dictionary whose words are not sorted in alphabetical order. As a function of the number, n, of words, what is the time complexity of searching for a particular word in this dictionary? Repeat the previous exercise for a dictionary whose words are sorted alphabetically. Compare your results with those for the previous exercise. 19. 20. Consider a football player who runs wind sprints on a football field. He begins at the 0-yard line and runs to the 1-yard line and then back to the 0-yard line. Then he runs to the 2-yard line and back to the 0-yard line, runs to the 3-yard line and back to the 0-yard line, and so on until he has reached the 10-yard line and returned to the 0-yard line. a. How many total vards does he run? b. How many total yards does he run if he reaches the n-yard line instead of the 10-yard line? c. How does his total distance run compare to that of a sprinter who simply starts at the 0-yard line races to the n-vard line? 20% Page 149 c1898

Explanation / Answer

14.) for loop in method1 runs n times irrespective of any values of array. and for each iteration of index, it calls the method privateMethod which iterates from index to n-1 which in turn runs like

n + n-1 + n-2 + ...+ 1 times which gives O(n^2).No there is no best and worst case as privateMethod1 in anyways search for min value throughout the array.

16.) In order to find out the values of n for which program A will execute faster than program B, we need to find out the value of n for which 2^n > 1000*n^2. For n>=19, 2^n > 1000*n^2. So for n>=19, program A will execute faster than program B.

18.) Suppose there are n words in dictionary and in worst case length of a word is 'm'. So, in worst case, we will required O(nm) time to search the word while in best case, we will require only O(m).

Hope it helps, do give your valuable response.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.