Хотя (несколько условий) Анализ сложности

Question

Очевидно, что некоторое время (i

Но что, если у меня есть время l oop, такое как :

while (counter != k && !found) {
   if (some condition)
     found = true;
   else
     counter++;
}

Как бы рассчитать сложность времени наихудшего случая, если я не знаю, когда найден будет установлен как истина?

Answer 1

Сложность по времени вышеупомянутого l oop будет O(k), и она не зависит от переменной found. Как и в худшем случае, счет будет работать до k, и это тоже будет средний случай.