Explain why each is wrong or right Identify what is true: An algorithm with amor

Question

Explain why each is wrong or right

Identify what is true: An algorithm with amortized complexity of O(Nlog(N)) can have individual operations that grows as N"N The input is essential when determining the worst and best case performance of an algorithm Tilde and Big-Oh analyses serve to determine how the worst case of an algorithm grows when the size of the problem grows Tilde-notation is the same as Big-Oh notation Amortized complexity means that the cost of executing costly operations can be amortized over less costly operations An algorithm that is Big-Omega(N) is always faster than a O(NlogN) algorithm for large When determining tilde approximations and/or the Big-Oh classification of a problem one should, in most cases, determine the "inner loop" of the algorithm An O(log(N)) algorithm is always faster than an O(N) algorithm for all N

Explanation / Answer

(a) It is true because the importance of Amortized analysis is to make the O(n*n) complexity as O(nlogn). Means Amortized analysis makes the worst case time complexity better.

(b) Yes , It is also true and it also very obvious because passing of different inputs is the only way to find the worst case and best case time complexity of any algorithm.

(c) Yes , It is true because Big-Oh works for only upper bound means only for finding worst case whereas Tilde Notation is used for both upper and lower bound also. So , both finds worst case time complexity for input size.

(d) False , Because Big-Oh works for only upper bound means only for finding worst case whereas Tilde Notation is used for both upper and lower bound also. And one more thing is that Tilde notation doesn't ignore the constants whereas BigOh ignores the constants.

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

---

---

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