Can anyone help with the big O notation?
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 imputation won't result in infinite loops
I understand how the method goes, but I can't figure out how the method is represented. For example, if the value was 0.00000009 or 9e-8, the method would call printScientificNotation (value * 10, powerOfTen - 1); eight times and System.out.println (value + "x 10 ^" + powerOfTen); once.
So it is called the recursive exponent for e. But how can I represent this with a big O notation?
Thanks!
a source to share
Is this a trick? This code will return infinitely for some of its inputs (e.g. value = -1.0, powerOfTen = 0), so its runtime is not O (f (n)) for any finite function f (n).
Edit . Assuming value > 0.0
...
The execution time (or depth of recursion if you prefer to look at it that way) does not depend on the value powerOfTen
, only on value
. For input value
in the range [1.0, 10.0), the execution time is constant, so O (1), For value
in [10.0, + infinity), you divide value
by 10 for each recursive call to value < 10.0
, so the execution time is O (log ten( value
)). A similar argument can be made for value
in the range (0.0,1.0), but note that log tenvalue
is negative for this case. Thus, your final answer may involve an absolute value operation. Then you might be wondering if you need to specify the base of the logarithms in the context of asymptotic complexity analysis. Hope you can take it from there!
a source to share