Question

Which of the following functions are O(n³)?

a) 12n³ +6n² +3n+1
b) n³ log(n)+2n+1
c) log₃ (n²⁰²³)+23n
d) n² / 2

Answer 1

To determine which functions are O(n³), analyze their growth rates compared to n³. Functions a) and b) are O(n³), while functions c) and d) are not.

Step-by-step explanation:

To determine which of the given functions are O(n³), we need to analyze their growth rates compared to n³. Big O notation is used to describe the upper bound or worst-case complexity of an algorithm or function.

1. a) 12n³ +6n² +3n+1: This function is O(n³) because the term with the highest degree is n³.
2. b) n³ log(n)+2n+1: This function is also O(n³) because the term with the highest degree is n³.
3. c) log₃(n²⁰²³)+23n: This function is not O(n³) because the dominant term log₃(n²⁰²³) does not have a degree of n³.
4. d) n² / 2: This function is not O(n³) because the highest degree term is n².

Therefore, functions a) and b) are O(n³) while functions c) and d) are not.