Анализ Big-O с функциями внутри функций

Я не понимаю, как работает Big-O при работе с функции внутри функций (при анализе наихудшего случая). Например, что, если у вас есть что-то вроде:

for(int a = 0; a < n; a++)
{
    *some function that runs in O(n*log(n))*
    for(int b = 0; b < n; b++)
    {
        *do something in constant time*
    }
}

Будет ли весь этот блок работать за O (n ^ 2 * log (n)), потому что в первом цикле for у вас есть O (n) и O (n * log (n)), поэтому O (n * log (n)) больше, и, следовательно, тот, который мы берем? Или это O (n ^ 3 * log (n)), потому что у вас есть O (n) и O (n * log (n)) во внешнем цикле for?

Любая помощь приветствуется! Спасибо!

5
задан Mason 19 September 2011 в 23:57
поделиться