SammiA - 2 months ago 13

Javascript Question

function NumberComplement(num) takes a decimal number ,converts it to a binary number, then inverts each binary digits , then converts the inverted binary number back to a decimal number.

my solution is

`NumberComplement(num){`

let bin= num.toString(2).split('').map( x => 1-x ).join('')

return parseInt(bin,2)

}

what is the time complexity for this function and why?

(the part that confused me is the map function , where num is already converted from an integer to an array made of 0s and 1s, and we know that the length of array is log(num)+1, so the function iterate log(num)+1 times , which makes the time complexity O(log(n))?........or am I overthinking it? is it simply O(n)?

Thank you so much for your time!

Answer

Let's assume for a second that `num`

can go to infinity. You then have these function calls involved:

```
| Function | Asymptotic time complexity | Motivation |
|--------------|----------------------------|------------------------------------------------------------------------------------------------------|
| .toString(2) | O(log n) | Number of bits in num |
| .split | O(log n) | Number of characters from .toString, which is equal to number of bits in num |
| x => 1-x | O(1) | x is either 0 or 1 so this does not vary with the size of n |
| .map | O(log n) | The anonymous function applied to each element in the result from .split: O(1) * O(log n) = O(log n) |
| .join | O(log n) | Number of characters in the result from .map, which is equal to the number of bits in num |
| .parseInt | O(log n) | Number of characters in bin, which is equal to the number of bits in num |
```

Add them up:

```
.toString + .split + .map + .join + .parseInt =
O(log n) + O(log n) + O(log n) + O(log n) + O(log n) =
O(log n)
```

This is not true in Javascript, however, which have an upper bound of 53 bits for integers. With an upper bound on `n`

you always get a Big-O asymptotic time complexity of `O(1)`

.