2) Computing the Average time complexity for a real-world problem is difficult.

Question

2) Computing the Average time complexity for a real-world problem is difficult.

Explain why by referring back to the formula for computing A(n).

*Why?

----------------------------

3) Your friend is very excited about having found a sorting algorithm that

sorts in much less than W(n) = Theta(N^2)comparisons even though it corrects

only one bad pair per comparison. He thinks this is the fastest sort ever

and that he will get a Ph.D. tomorrow.

Please teach him why he is wrong.

*Answer:

----------------------------

4) Your friend says she can find a comparison based algorithm that searches

for an element in an ordered list in much less than W(N) = Theta(log N).

Please teach her why she is wrong.

*Answer:

----------------------------

5) Name 2 Divide and Conquer algorithms we studied in this class.

*Name:

*Name:

----------------------------

6) Describe 2 Space vs. Time decision cases

In what ways can each be called Space vs. Time?

*Example Algorithms: ________ vs.______________

*Reason:

*Example Data Structures: _________vs.____________

*Reason:

----------------------------

7) Name 2 greedy algorithms

*Algorithm for solving/finding:

*Algorithm for solving/finding:

Explanation / Answer

2. the average-case complexity of an algorithm is the amount of some computational resource (typically time) used by the algorithm, averaged over all possible inputs. It is frequently contrasted with worst-case complexity which considers the maximal complexity of the algorithm over all possible inputs.Complexity can be looked at from many angles.A computational problem is understood to be a task that is in principle amenable to being solved by a computer, which is equivalent to stating that the problem may be solved by mechanical application of mathematical steps, such as an algorithm.Thus its application to thereal world is quiet difficult.

5.2 divide and conquer algorithms are as follows:

6.In general, the amount of space used is less than the amount of time used because space can be reused and time cannot. For most applications, we focus on time complexity, since memory tends to be cheap compared to time (thee days). Sometimes, space is still an issue - particularly if the problem size is very large and the solution requires relatively low time complexity. (An example would be sorting very large (on the order of one-billion element) data sets.)

A simple space example - adding two arrays of integers. Assume our array size is N and A,B are input arrays.

7.2 greedy alogorithms are:

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

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