Beginning Java Data Structures and Algorithms

Activity: Converting Expressions to Big O Notations

Scenario

To convert the expression 3mn + 5mn⁴ +2n² + 6 to a big O notation, firstly we drop any constants from the expression, leaving us with mn+mn⁴+n². Next, we simply keep the highest order part, which results in O(mn⁴).

For each of the expressions found in Table 1.6, find the equivalent in big O notation:

Expression

3mn

5n + 44n2 + 4

4 + 5 log n

3n + 5n2 + 8

Table 1.6: Find big O equivalent

Aim

To apply notation rules to convert expressions into big O notations.

Steps for completion

1. Identify and drop the constants in the expression:
   • 3mn → No constants → 3mn
   • 5n + 44n² + 4 → 4 → 5n + 44n²
   • 4 + 5 log n → 4 → 5 log n
   • 3ⁿ + 5n² + 8 → 8 → 3ⁿ + 5n²
2. Drop everything except the highest-order ...