временная и пространственная сложность функции с бинарным поиском

Question

Я написал следующую функцию в Java;

int foo(int a[], int n) {
    int num1 = 1, num2 = 1; 
    while(num1 < n) {
        if (binarySearch(a,num1,num2) >= 0) {
            return num2;
        }
        num1 = 2 * num1;
        num2 = 2 * num2;
    }
    return 0;
}

Я пытаюсь выяснить временную и пространственную сложность этой функции.Я знаю, что временная сложность binarySearch равна O(logn), а пространственная сложность этой функции - O(1).С помощью этой информации я попытался вычислить эти вещи из функции foo.Я думаю, что временная сложность foo равна O((logn)^2), а сложность пространства O(1), но я не уверен в этом.Каков наилучший метод для расчета этих вещей?

Answer 1

Давайте проанализируем упрощенный цикл while без вызова binarySearch():

while(num1 < n) {
    num1 = 2 * num1;
}

Сколько шагов нужно выполнить в зависимости от n?

Как только вы ответитеВ этом вопросе ключом к окончательному решению является осознание того, что сложность цикла while умножается на сложность его тела.Это означает, что окончательный ответ является ответом на вышеуказанный вопрос времени log n.