1) What is the purpose of using asymptotic notation such as O, Omega and Theta i
ID: 3579068 • Letter: 1
Question
1) What is the purpose of using asymptotic notation
such as O, Omega and Theta instead of using
the exact number of comparisons done by a sorting algorithm?
i.e. why do we use O(n^2) instead of saying 2n^2 + 3n + 4
*Because we are only interested in
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 we discussed in this class.
In what ways can each be called Space vs. Time?
*Example Algorithms: ________ vs.______________
*Reason:
*Example Data Structures: _________vs.____________
*Reason:
7) Name 2 greedy algorithms we have learned in this class.
*Algorithm for solving/finding:
*Algorithm for solving/finding:
Explanation / Answer
Ans 1) There is a lot of difference between reality and computational model. Counting tha exact number of comparisons may be hard and wouldn't help in preparing precise results. To describe the running time simple functions should be used. That's why symptotic notation is prefered over exact number of comparisons i.e. O(n2) is preferred over 2n2 + 3n + 4.
Let us consider an example : 4n2 + 2n + 2
As you can see that the time complexity depend more on 4n2 than 2n + 2. Because 4n2 term is very high than 2n + 2. So its better to use O(n2) rather than 4n2 + 2n + 2 to describe the running time or time complexity of the equation.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.