Can someone help with big O notation?

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);
}

}

assuming that imputs will not lead to infinite loops

I understand how the method goes but I cannot figure out a way to represent the method. For example, if value was 0.00000009 or 9e-8, the method will call on printScientificNotation(value * 10, powerOfTen - 1); eight times and System.out.println(value + " x 10^" + powerOfTen); once.

So the it is called recursively by the exponent for e. But how do I represent this by big O notation?

Thanks!

Answer 1

Is this a trick question? That code will recurse infinitely for some of its inputs (for example, value=-1.0, powerOfTen=0), therefore its runtime is not O(f(n)) for any finite function f(n).

Edit: Assuming value > 0.0...

The run time (or recursion depth, if you prefer to look at it that way) does not depend on the value of powerOfTen, only on value. For an intial input value in the range [1.0, 10.0), the run time is constant, so O(1), For value in [10.0, +infinity), you divide value by 10 for each recursive call until value < 10.0, so the runtime is O(log₁₀(value)). A similar argument can be made for value in the range (0.0,1.0), but note that log₁₀ value is negative for this case. So your final answer might involve an absolute value operation. Then you might consider whether it's necessary to specify the logarithm base in the context of an asymptotic complexity analysis. Hopefully you can take it from there!