Also I was asked what the Big(o) of this was but had a hard time figuring it out— what is the time complexity of JavaScript reverse?
Now, I don't know much about Big O notation, but I'll give you my two cents about this issue.
First off, I don't think that the reverse()
is actually part of the complexity. Considering this is a built-in function and all you do is simply call it, it can be considered \$O(1)\$.
However, again, I don't think that is actually part of the time complexity; when the interviewer asked that, he/she was most likely referring to your algorithm.
To find the complexity of your algorithm, think of it like this: this function you have written is a function of number
; in Big O terms, number
would be your n
.
Now, basically, all you need to do is find how many "iterations" (not the real thing, but works in this case) your function does based on it's input. To find that, you need to look here:
while (difference <= number){
and here:
while(number > 0) {
Both of these loops involve the only argument number
(n
) and will run a certain amount of times based on this argument. Looking at these they both run the range of
0 to number
, only on powers of 2 in this range.
For example, if number
was 5000, then these would be the numbers, then you traverse:
1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096
both times (the first loop you go left to right, the second one you go right to left).
If you look further into this, you might be able to find a proper Big O notation to represent this.
Power (look-up) Table!
Looking over your algorithm, I see that you are using Math.pow
a lot. While this is a nice method and it is helpful, it can be very inefficient (especially if used too many times).
Focusing only on n
, your algorithm does this:
- Set
n
to 0
- Increment
n
to a limit, calculating Math.pow
each increment.
- Decrement
n
back down to zero, calculating Math.pow
twice for each decrement (except for the first).
So, if the limit ends up being 10 in this case, you would have called Math.pow
28 times.
A way to speed this up would be to create an array and store all the Math.pow
s in it when you are first incrementing up to the limit. Then, when you are decrementing, simply reference the table for the value. This would reduce those 28 calls down to only 10.
In your first loop:
while (difference <= number){
n++;
powArr[n] = difference = Math.pow(2, n);
binaryArr.push(0);
}
Then, in your second loop:
while(number > 0) {
var pow = powArray[n];
if (pow <= number) {
binaryArr[n] = 1;
number -= pow
}
n--;
}
Note: I added in a pow
variable so you don't have to access the array twice.
Now, your code doesn't have to call this expensive Math.pow
as often, overall increasing the speed of your code.