Question

The following functions have been calculated as the runtime complexity of various algorithms. Identify the Big-O complexity, and provide witness values to support your answer. Clearly highlight your answer and show any working out you do.

i. f(n) = 13 + 3n2 – 9n ii.

f(n) = 3n.log2n + 7n

iii. f(n) = nn + 2n5 – 7

iv. f(n) = 2log2n + 4n

v. f(n) = 20 + 2n4 – n2 +n

vi. f(n) = 7n3/4 +3n

Answer 1

Calculating the big-O complexity of a function is easier than calculating it for the algorithm. In case of algorithm you need to take care of so many things like array, loops, nested loops, etc and if you miss any your calculation may go wrong. So,

To calculate the Big-O complexity of a function, these are the points you should keep in mind:

• Eliminate all the constants
• Exclude the non-dominants

Lets have a look at the questions:

(i): f(n) = 13 + 3n²  +9n

O(f) = O(13) + O(3n²) + O(9n) ----- GIVEN

O(f) = O(3n²) + O(9n) ----- ELIMINATION OF CONSTANTS

O(f) = O(n²) + O(n) ------ ELIMINATION OF CONSTANTS

O(f) = O(n²) ----- EXCLUSION OF NON-DOMINANT

So, the Big-O complexity of the given function is O(n²)..

(ii): f(n) = 3n.log2n + 7n

O(f) = O(3n log²n) + O(7n) ----- GIVEN

O(f) = O(n log²n) + O(n) -----   ELIMINATION OF CONSTANTS

O(f) = O(n log²n) -----   EXCLUSION OF NON-DOMINANT

So, the Big-O complexity of the given function is O(n log²n)..

(iii): f(n) = nn + 2n5 – 7 (Considering nn as n²)

O(f) = O(n²) + O(2n⁵) + O(7) ----- GIVEN

O(f) = O(n²) + O(2n⁵) -----   ELIMINATION OF CONSTANTS

O(f) = O(n²) + O(n⁵) -----   ELIMINATION OF CONSTANTS

O(f) = O(n⁵) -----   EXCLUSION OF NON-DOMINANT

So, the Big-O complexity of the given function is O(n⁵)..

(iv) : f(n) = 2log2n + 4n

O(f) = O(2 log²n) + O(4n) ----- GIVEN

O(f) = O( log²n) + O(n) ----- ELIMINATION OF CONSTANTS

O(f) = O(n) ----- EXCLUSION OF NON-DOMINANT

So, the Big-O complexity of the given function is O(n)..

(v): f(n) = 20 + 2n4 – n2 +n​​​​​​​

O(f) = O(20) + O(2n⁴) + O(n²) + O(n) ----- GIVEN

O(f) = O(2n⁴) + O(n²) + O(n) ----- ELIMINATION OF CONSTANTS

O(f) = O(n⁴) + O(n²) + O(n) ----- ELIMINATION OF CONSTANTS

O(f) = O(n⁴) ----- EXCLUSION OF NON-DOMINANT

So, the Big-O complexity of the given function is O(n⁴)..

(vi): f(n) = 7n3/4 +3n​​​​​​​

O(f) = O(7n^3/4) + O(3n) ----- GIVEN

O(f) = O(n^3/4) + O(n) ----- ELIMINATION OF CONSTANTS

O(f) = O(n) ----- EXCLUSION OF NON-DOMINANT

So, the Big-O complexity of the given function is O(n)..

I hope the answers help..

​​​​​​​Thanks!