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

In the given question there are 3 assignment operations which are to be considered,they are present at line 5,10,16.

The time complexity due to assignment at line 5 would be

T1=k(n2);{since it is inside two for loops which run from 1 to n}

The time complexity due to assignment at line 5 would be

T2=k2(n2log(n)) ;{since it is inside two for loops which run from 1 to n and 1 for loop for where iterrator value decreses by half after every iteration}

the time complexity of the for loop at line 16 will be

T3=k(n*i2);

T3=k(n*(n(n+1)(2n+1)/6));

T3=k4(2n4+3n3+n2)

hence the worst case time complexity of this algorithm would be

T=O(n4)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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