What's the Big-O of this base converter?

Question

My answer is O(D + R). Is it correct?

I want to figure out the Big-O of this code. I am doing an independent coursework on data structures and algorithms.

This code is lifted from the book "Data Structure and Algorithms in JavaScript" by Ms. L Groiner, PacktPub, which I am studying right now.

Please see below:

function baseConverter(decNumber, base) {
   var remStack = new Stack(), //instantiate class, define variable, O(1)
   rem, // define var, O(1)
   baseString = '', //initialize, O(1)
   digits = '0123456789ABCDEF'; //initialize, O(1) 

   while(decNumber>0) { //loop, D times:
       rem = Math.floor(decNumber % base); //modulo/Math/assignment, O(1) 
       remStack.push(rem); //push to stack, O(1)
       decNumber = Math.floor(decNumber / base); //divide, Math, assignment, O(1)
   }


   while(!remStack.isEmpty()){ //loop, R times: 
       baseString += digits[remStack.pop()]; //pop/index/Math/addition assignment, O(1)
   }
   return baseString; // O(1)
}

I simplify each operation, line-by-line, like so:

4 * O(1) + D * 3 * O(1) + R * O(1) =
3 * O(D) + 1 * O(R) =
O(D) + O(R) = O(D + R)

I have gone over my own web development notes and looked at various books. But I can only form snippets and deduce from it. I would like to find a standardized framework or at least build it in my mind to be able to state the run time in Big-O correctly. Giving me feedback on this, helps me to do so.

Your function takes parameters `decNumber` and `base`. What is *n* equal to, in your analysis? — John Kugelman, Feb 04 '17 at 06:30
(No, your answer is not correct. Being more precise about what *n* is will help pinpoint the error.) — John Kugelman, Feb 04 '17 at 06:32
@JohnKugelman. I renamed my N to distinctly represent the two different while loops. I went back to the Cracking the Coding Interview book by G L McDowell. It reads that if the algorithm is in the form of, "do this, and then when you're all done do that", add the run time. First while loop, pushes remainder in a stack; and then divides the decimal number into 2. This goes on until decimal number is greater than 0. Afterwhich, second while loop starts with popping elements from remStack, using that as index to pluck out the digits then filling out the base string. Return base string. — Anna S, Feb 04 '17 at 21:06
How many times can you divide `decNumber` by `base` before it hits 0? Figure out the Big-O in terms of `decNumber` and `base`. That's the number of times the first loop will iterate. The second loop iterates the same number of times as the first. — John Kugelman, Feb 04 '17 at 23:38
@JohnKugelman, it depends on what the value of the base is. The higher the value of the `base` (like base-16) is, the lower the number of times the `decNumber` can be divided. The first loop will iterate lesser, if this was the case. On the other hand, if the `base` was lower (like base-2) the first loop will iterate more. — Anna S, Feb 05 '17 at 22:31
There's a formula for it. Hint: It's better than O(baseNumber). — John Kugelman, Feb 06 '17 at 01:23
Is it O(1)? That's the only one I think which is better than O(baseNumber). — Anna S, Feb 06 '17 at 04:53
How many digits does `decNumber` have? Do you know a formula for the number of digits a number has? That's how many times the two loops will iterate. — John Kugelman, Feb 06 '17 at 04:59

score 0 · Accepted Answer · edited May 23 '17 at 12:10

Runtime complexity of the first loop:

 while (decNumber > 0) {
       rem = Math.floor(decNumber % base);
       remStack.push(rem);
       decNumber = Math.floor(decNumber / base);
 }

This loop iterates as often as decNumber can be divided by base. Thus, the number of iterations is roughly log_base(decNumber).

During each iteration you perform an array push operation. For simplicity we assume it runs in constant time.

The second loop runs as often as array elements have been pushed onto remStack which equals the number of iterations of the first loop.

The overall runtime complexity is thus proportional to roughly 2 * log_base(decNumber) which equals O(log(decNumber)).

This holds as long as modulo and division operations on decNumber can be performed in constant time (which is true for the limited precision JavaScript number datatype) on typical hardware.

What's the Big-O of this base converter?

1 Answers1