Analysis of Algorithm (please write the answer on the computer or in a readable

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 X

Explanation / Answer

# of operations

if n is from 1 to 2n:

n2 operations (line 5 -> y<-y+1 and 2 loops line 2 and 4)

if n is from 2n to 3n-1:

nlog(n) operations (line 10, first loop in line with n iterations and 2nd loop in line 9 with log(n) iterations)

if n is 3n:

3 loops with 1st (line 2), 2nd (line 14) and 3rd(line 15) loop having 1+2+3...n iterations so it will have n3 iterations

TIME COMPLEXITY:

Average case: when X is from 1 to 2n i.e it take only O(n2) ---> first if condition

Worst case: when X is 3n i.e. it takes O(n3) --> else condition

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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