CODEWITHSUNDEEP
algorithmbig-oanalysis
Kuni_Leqa
Kuni_Leqa

Reputation: 35

Big O order of a function

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

Upvotes: 3

Views: 246

Answers (1)

Codor
Codor

Reputation: 17605

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).

Upvotes: 3

Related Questions