Analysis of Algorithm (please write the answer on the computer or in a readable
ID: 3598866 • Letter: A
Question
Analysis of Algorithm
(please write the answer on the computer or in a readable handwriting.)
Do a fine (exact) analysis and calculate the number of operations for the worst case and average case. Express the worst case and average case time complexities of the function using the big O notation. The basic operations are assignments each of which consumes 1 unit of time. You can ignore the condition checks and the assignments in the loop headers. You may assume that X is a uniformly distributed random number between 1 and 3n. n is an integer. 1: function Q1(X (any number from 1 to 3n), n) 2 3: for 2 0 to n-Ido if XExplanation / Answer
Answer:-
X is regularly circulated random variable between 1 to 3n
Thus the probability of execution of first if statement (line no. 3-6) is 2n/3n = 2/3
And the probability of execution of second if statement (line no. 7-12) is ((3n-1)-(2n+1) +1)/3n = (n-1)/3n
Similarly the probability of execution of last if statement (line no. 13-19) is 1/3n
The number of operations in first if statement (line no. 3-6) is n
And the number of operations in second if statement (line no. 7-12) is n.logn
And the number of operations in last if statement (line no. 13-19) is (12+22+.....+ (n-2)2)/3n
= ((n-1)(n-2)(2n-3))/6 x 1/3n
= ((n-1) (n-2) (2n-3))/18n
Worst Case Analysis: Worst case condition happens if each time in the loop, the last if statement (line no. 13-19) is executed.
Thus number of operations in the worst case is n x ((n-1) (n-2) (2n-3))/18n = ((n-1)(n-2)(2n-3))/18 = O(n3)
Average Case Analysis:
From the above discussion with probabilities, we have the number of operations in average case is
(2/3) xn + ((n-1)/3n) x (n.logn) + (1/3n)x(((n-1)(n-2)(2n-3))/18n)
= 2n/3 + ((n-1)logn)/3 + ((n-1)(n-2)(2n-3))/(54n2)
= O (n.logn)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.