SammiA SammiA - 1 month ago 8
Javascript Question

what is the time complexity of this NumberComplement function?

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).