Given an algorithm that solves a problem in three phases The

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

Solution

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(2n² - 3n)

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

= O(n²) - O(n)

= O(n²)

b) O(n! + 2ⁿ)

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

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

c) O(5n² + nlogn)

= O(n²) + O(nlogn)

= O(n²)

d) O(n^1.001 + nlogn)

= O(n^1.001) + O(nlogn)

= O(nlogn)

e) O(5n³ - 3n²logn + 2n)

= O(n³) - O(n²logn) + O(n)

= O(n³) [Since n³>n²logn for all n>1]