1) What is the purpose of using asymptotic notation \"such as O, Omega and Theta
ID: 3576725 • 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
1) 1) Asymptotic notations like Omega, Theta, or BigO are used to calculate the time complexity, how much time does it take in worst case, best and average case and it depends on maximum number of items in the equation, loop or any expression like here 2n^2 +3n+4 , the maximum value of n is n^2 hence we just take it as this will give the time estimate.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.