Big O order of a function

user_10407218 0
Viewed 116

I'm doing some practice questions on Big O notation and came across this question. What is the Big O order of function () = ^2 + log2() + log2(). Show your working.

My answer is O(n^2) because it's the term with the highest degree. However, I'm not really sure how to show it. Am I right by saying that it has to be proven like this -> f(n) is an element of O(n^2). So far, I've only done questions like n^2 + 2n + 1 and I have to find c and k values. I'm not quite sure how to do this one. Can anyone help me out, please?

Thanks

analysis big-o algorithm
1 Answers

Let c := 3 and k := 1. Let n >= k, i.e. n >= 1. We obtain

f( n ) = n*n + n*log(n) + log(n)  // definition of f
      <= n*n + n*n      + n      // n >= k = 1
      <= n*n + n*n      + n*n    // n >= k = 1
       = 3*n*n
       = c*n*n

which means that f \in O(n*n).

user_33554760
Related