Может ли кто-нибудь помочь с большой нотацией?

Question

void printScientificNotation(double value, int powerOfTen)
{
if (value >= 1.0  &&  value < 10.0)
{
    System.out.println(value + " x 10^" + powerOfTen);
}
else if (value < 1.0)
{
    printScientificNotation(value * 10, powerOfTen - 1);
}
else     // value >= 10.0
{
    printScientificNotation(value / 10, powerOfTen + 1);
}

}

при условии, что импорты не приведут к бесконечным циклам

Я понимаю, как работает метод, но я не могу найти способ представить метод. Например, если значение было 0,00000009 или 9e-8, метод вызовет printScientificNotation (значение * 10, powerOfTen - 1); восемь раз и System.out.println (значение + "x 10 ^" + powerOfTen); один раз.

Таким образом, он вызывается рекурсивно показателем степени для e. Но как я могу представить это большими буквами O?

Спасибо!

Answer 1

Это вопрос с подвохом? Этот код будет бесконечно повторяться для некоторых его входов (например, значение = -1,0, powerOfTen = 0), поэтому его время выполнения не равно O (f (n)) для любой конечной функции f (n).

Редактировать : Предполагается, value > 0.0 ...

Время выполнения (или глубина рекурсии, если вы предпочитаете смотреть таким образом) не зависит от значения powerOfTen, только от value. Для начального входа value в диапазоне [1.0, 10.0) время выполнения является постоянным, поэтому O (1), Для value в [10.0, + бесконечность) вы делите value на 10 для каждой рекурсивной звоните до value < 10.0, поэтому время выполнения равно O (log ₁₀ (value)). Аналогичный аргумент можно сделать для value в диапазоне (0,0,1,0), но обратите внимание, что log ₁₀ value является отрицательным для этого случая. Таким образом, ваш окончательный ответ может включать в себя операцию абсолютного значения. Затем вы можете подумать, нужно ли указывать базу логарифма в контексте анализа асимптотической сложности. Надеюсь, вы можете взять его оттуда!