Question

Calculate the Big-O time complexity. Show work

7. 0.1n + 100n^2

8. 100n + 0.01n^2

9. 100n log3 n + n^3 + 100n

10. n + n/2 + n/4 + · · · + 1

Answer 1

7) 0.1n is linear in n and 100 n^2 is quadratic.

So Big -O time complexity is O(n^2) as it is the highest order in the given notation.

8) 100n is linear in n and 0.01n^2 is quadratic

So Big -O time complexity is O(n^2) as it is the highest order in the given notation.

9) 100n log3n (here 100n is linear in n, log3n results in constant), n^3 is cubic and 100n is again linear in n.

The highest order in the notation 100n log3n + n^3 + 100n  is n^3. Therefore, the given notaion has a time complexity of O(n^3).

10) n + n/2 + n/4 + · · · + 1

In this noation each element (i.e., n, n/2, n4/4, ... is linear in n)

Therefore the time complexity of n + n/2 + n/4 + · · · + 1 is O(n).