Given a problem A with problem size n, student John devised an algorithm for the

Question

Given a problem A with problem size n, student John devised an algorithm for the problem with time complexity O(n^2.5 log^2 n), student Mary proposed an algorithm for the problem with time complexity of O(n^2 log^4 n), and student Xiaomin devised an algorithm for it with time complexity of O(n^2.0001 log log n) while the lower bound of problem A is ohm (n^2 log log n). Among the three algorithms, which one is the best in terms of theirs time complexity? Order the three algorithms in terms of the upper bounds on their running time from the highest to the lowest.

Explanation / Answer

Please give the thumbs up, if it is helpful for you!!. Let me know if you have any doubts.

Answer:

John's algorithm time complexity is O(n2.5 log2n)
Mary's algorithm time complexity is O(n2log4n)
Xiaomin's algorithm time complexity is O(n2.0001loglogn)

Among these three alogorithms Xiaomin's algorithm time complexity is best. Because it is close to the lower bound of the problem and take less time to execute among three algorithms.

Order time complexity from highest to the lowest:

O(n2.5 log2n) > O(n2log4n) > O(n2.0001loglogn)

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

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