38.7k views
3 votes
Calculate Big Oh for the following f(n): 1 f(n)=6n²+3 2 f(n)=n²+17n+2 3 f(n)=n³+100 n²+n+10 4 f(n)=logn+n 5 f(n)=logn+nlogn+n³+n!

User Birish
by
8.3k points

1 Answer

6 votes
Answer:

1. f(n) = 6n² + 3

We can see that f(n) is a polynomial of degree 2. Therefore, f(n) is O(n²) by definition of Big-O.

2. f(n) = n² + 17n + 2

Again, f(n) is a polynomial of degree 2. Therefore, f(n) is O(n²) by definition of Big-O.

3. f(n) = n³ + 100n² + n + 10

Since f(n) is a polynomial of degree 3, we can say that f(n) is O(n³) by definition of Big-O.

4. f(n) = logn + n

We can see that n grows faster than logn. Therefore, we can say that f(n) is O(n) by definition of Big-O.

5. f(n) = logn + nlogn + n³ + n!

We can see that the term n! grows much faster than any other term in the expression. Therefore, we can say that f(n) is O(n!) by definition of Big-O.
User JCBrown
by
8.5k points
Welcome to QAmmunity.org, where you can ask questions and receive answers from other members of our community.

9.4m questions

12.2m answers

Categories