Я не понимаю, как работает 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?
Любая помощь приветствуется! Спасибо!