A reminder that the work you paw In should be your own work. For the assignment

Question

A reminder that the work you paw In should be your own work. For the assignment you may work Is terms of two. Each student's information should be included in the program headers. If you find help, on Google for example, then you MUST credit the source. Do Question 5 on page 321. Write a program that fills an array with 20 random integers to test your function. Have your program display the array before it is sorted and again after calling Sort Integer Array. Do Question 6 on page 321. Do Question 13 on page 333. There is no need to prove that the formula compute the nth Fibonacci number. Theory Questions Suppose we have determined that this loop is where our algorithm does the most work: How would we express the running time in Big Oh notation? You are given the information that the running time of one algorithm is proportional to N log N and the running time of another algorithm Is proportional to N2. What does that statement imply about the relative performance of the algorithms? For what values of N is 10N log N > 2N2?

Explanation / Answer

Lets hope you are asking the theory problems 1. Its O(n^3) as it has 3 loops of O(n) nested within one another 2.One is O(n^3) and another is O(Nlog N) it may happen that O(n^3) is initially better performing that the O(N log N) {this is a very rare scenario, if algo of O(N^3) is required then the constants involved here are generally quite large, constants in NlogN are generally not very large} but generally O(N log N) performs better than O(N^3) in most of the cases but as N grows larger O(Nlog N) has a very very huge performance advantage over the O(N ^ 3) algorithm 3. This is an easy calculation problem 10 N log N > 2 N^2 iff 5 log N > N hence 5 > Nlog N, we can prove that the function on the right is a strictly increasing function if the base of the log > 1 (just differentiate it and its > 0) So if base of log is 2 : N < 23 if base is e : N < 13 if base is 10: it holds only N = 1

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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