Analysis of Algorithm Do a fine (exact) analysis and calculate the number of ope

Question

Analysis of Algorithm

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

Time complexity analysis for given pseudocode:

Overall the program has loop running from 0 to n-1 i.e. It runs for n times.

i.e. It will go down in m, m/2, m/4, m/8 …. 1 so it will run for log(n)times.

Now we will use the observations from above to compute the worst and average case.

Clearly slowest running part is C, having two for loops. And there is one fixed for outer for loop.

Hence by normal multiplication to complete all the iterations of part C will take n x n x n times [ generalizing the i x i ]

In big O notation:

Here part- A takes O(n2) time, B takes O(n2logn) and C. O(n3).

Average=(O(n2+n2logn+n3))/n

Which will be greater than the n2 (as n3, the longest will decompose to n2).

So Average case is: (n2)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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