Big O. Вложенный цикл с if

Question

В общих чертах, ситуация следующая:

Я имею такой код:

for(i = 0; i < 10; i++)
{
     if(condition)
     {
         for(...){ }
     {
     else
     {
         for(...){ }
     }

}

И такой:

void function(int b)
{
     if(b <= 0)
        return;
     if(condition)
     {
        function(b - 1);
        function(b - 1);
     }
}

Как должны рассчитываться сложности этих алгоритмов?

Answer 1

Первый код — нет никаких данных. Мало ли что у вас в циклах крутится... Поэтому просто нет данных.

Второй — ну, пусть время работы f(b) равно t(b). Тогда в худшем случае (condition всегда 'true') имеем:

t(b) = 2*t(b-1)

(временем проверки условия пренебрежем). Вот и выходит, что если t(0) = C (какой-то константе), то t(n) = С*2^n. Вот и ответ: O(2ⁿ).