Большой О порядок функции

Question

Я делаю несколько практических вопросов по обозначению Big O и наткнулся на этот вопрос. Что такое большой О порядок функции ? (?) = ? ^ 2 + ? log2 (?) + log2 (?). Покажите свою работу.

Мой ответ O (n ^ 2), потому что это термин с наивысшей степенью. Однако я не совсем уверен, как это показать. Прав ли я, говоря, что это должно быть доказано так -> f (n) является элементом O (n ^ 2). До сих пор я задавал только вопросы типа n ^ 2 + 2n + 1, и мне нужно найти значения c и k. Я не совсем уверен, как это сделать. Кто-нибудь может мне помочь, пожалуйста?

Спасибо

Answer 1

Пусть c := 3 и k := 1. Пусть n >= k, т.е. n >= 1. Получаем

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

, что означает, что f \in O(n*n).