Given an algorithm that solves a problem in three phases. The first phase takes

Question

Given an algorithm that solves a problem in three phases. The first phase takes O(100n) to input the data of size n. The second phase takes O(n log n) to process the data. The third phase takes O(log n) to output the data. What is the complexity of the algorithm? If the data size is 10, which phase is most likely to take the longest time to execute? For each of the complexity expression below, determine its overall complexity. For example, given expression 2n + 3n, the overall complexity should be O(n). 2n^2 - 3n n! + 2^n 5n^2 + n log n n^1.001 + n log n 5n^3 - 3n^2 log n + 2n

Explanation / Answer

1.

a) The complexity of the algorithm = O(100n) + O(nlogn) + O(logn)

= O(n) + O(nlogn) + O(logn)

= O(nlogn) [Since, for all n>=c, O(n)<O(nlogn) and also for all n>=d, O(logn)<O(nlogn)

Hence, O(nlogn)

b) For data size 10, time for first operation = 100n = 1000

For data size 10, time for second operation = nlogn = 10*log10

For data size 10, time for third operation = logn = log10

Hence, the first phase with complexity O(100n) will take the most time for data size of 10.

2.

a) O(2n2 - 3n)

= O(2n2) - O(3n)

= O(n2) - O(n)

= O(n2)

b) O(n! + 2n)

= O(n!) + O(2n)

= O(n!) [Since, factorials grow much faster than exponentials. If in doubt, see that 10! = 10*9*8*...*1 whereas 210=2*2*..*2(10 times)]

c) O(5n2 + nlogn)

= O(n2) + O(nlogn)

= O(n2)

d) O(n1.001 + nlogn)

= O(n1.001) + O(nlogn)

= O(nlogn)

e) O(5n3 - 3n2logn + 2n)

= O(n3) - O(n2logn) + O(n)

= O(n3) [Since n3>n2logn for all n>1]

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

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