In this question you will analyze the worst-case running time of the pseudocode
ID: 3843774 • Letter: I
Question
In this question you will analyze the worst-case running time of the pseudocode function vac. For each subquestion, give the running time in asymptotic notation using a function on n, the number of items in P. Be sure to justify your answers.
(a) m is in O(1), and the cost of FeatureAtPoint is in O(1).
(b) m is in O(n), and the cost of FeatureAtPoint is in O(1).
(c) m is in O(n), and the cost of FeatureAtPoint is in O(n).
function vac(x, y, m): for ifromxtox+ m for j from y to y+ m if Feature AtPoint(i,J False: return False return TrueExplanation / Answer
Overall time complexity of given code depends on time required by each loop and function FeatureAtPoint.
a.) since m is O(1). Therefore, each loop runs for constant amount of time and cost of FeatureAtPoint is also O(1). So, overall worst-case running time of pseudo-code is O(1).
b.) since m is O(n). Therefore, each loop runs for 'n' times and cost of FeatureAtPoint is O(1). So, overall worst-case running time of pseudo-code is O(n*n) i.e., O(n^2).
c.) since m is O(n). Therefore, each loop runs for constant amount of time and cost of FeatureAtPoint is also O(n). So, overall worst-case running time of pseudo-code is O(n*n*n) i.e., O(n^3).
Hope it helps, feel free to comment in case of any query.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.