0
$\begingroup$

Suppose you're given $x,y$ integers s.t. $x \leq y$. I want to find all values $\in [x, y]$ (inclusive) that are a power of $2$.

There's a $O(\log y)$ approach, where you just start at $1$, and keeping multiplying by $2$ until you get to the first value that is $\geq x$. Then you can start storing these values until you get to a power of 2 that is $> y$.

There's another approach that I believe is $O( \log (\log b))$, but I am not certain. The idea I am thinking of is rather than multiplying by $2$ each time, you square the value. So you'd have to start at $2$, then check $4$, then $16$, then $256$ and so on until you find the first value that is $>= x$. Say this value is $k$ where $k \geq x$. I believe finding $k$ is $O(\log(\log b))$. Is that correct?

After finding $k$, you can keep dividing by $2$ until you get a value that is $< x$ and store all the values along the way (unless it's greater than $y$). Then you can do this in the upward direction and keep multiplying by $2$ until you get to a value that's greater than $y$. It's not clear to me what the complexity of this step is. I want to say it's $O(\log (\log b))$ as well, but it seems it may actually be $O(\log b)$.

$\endgroup$
9
  • $\begingroup$ Why not simply find formula and obtain $O(1)$ complexity? $\endgroup$
    – zkutch
    Commented Aug 16, 2021 at 2:28
  • $\begingroup$ @zkutch This is more of a complexity analysis question than "what's the best algorithm to solve this?" With that said, what's the formula? $\endgroup$
    – anonuser01
    Commented Aug 16, 2021 at 2:29
  • $\begingroup$ Calculating amount by formula is also algorithm, not only finding it by loop. Using loop in such cases, when exists formula for answer is worst what can be done. $\endgroup$
    – zkutch
    Commented Aug 16, 2021 at 2:31
  • $\begingroup$ @zkutch I don't really see what this has to do with my question. I'm asking about the time complexity for my specific algorithm, not how to solve it in a different way. $\endgroup$
    – anonuser01
    Commented Aug 16, 2021 at 2:33
  • $\begingroup$ I want only warn against a situation where using a loop is unreasonably expensive - you will not count the sum of numbers in a loop if/when you know the answer by the formula, right? the rest is, of course, your business and I wish you the best of luck. $\endgroup$
    – zkutch
    Commented Aug 16, 2021 at 2:39

2 Answers 2

2
$\begingroup$

Yes, that is correct, in a sense, but there is also a sense in which it is not correct.

You want to find $j$ such that $2^j \in [x,y]$. The naive algorithm uses linear search on $j$. Your proposed algorithm amounts to binary search on $j$ (starting with iterative doubling). So your analysis is correct, that it uses $O(\log \log y)$ iterations.

The shortcoming of your analysis is that you assume each iteration can be done in $O(1)$ time. This might be accurate, or it might not, depending on the specific theoretical model of computation you are using. In practice, it is probably not reasonable, if $x,y$ are very large, as the running time of each iteration is not $O(1)$. For instance, squaring a $n$-bit number takes $O(n)$ time (in many reasonable ways of measuring running time); here we have $n=\lg y$, so each iteration takes $O(\log y)$ time, for a total running time of $O((\log y)(\log \log y))$ time (at least under one way of measuring running time).

Another way to put it is that it takes $O(\lg y)$ time even just to read the input or produce the desired output, because the output will be $\Omega(\lg y)$ bits long, and the time it takes to print such an output is proportional to its length.

$\endgroup$
3
  • $\begingroup$ That makes sense. I was assuming each iteration is in $O(1)$ time. How about the latter half of the question (after finding $k$)? Also note that my $k$ is different from yours. I defined $k$ to be the first value $\geq x$ after starting from $2$ and continuously squaring the value. To avoid mixing up variables, I'll use the variable $c$ to represent this value. To find $c$, and assuming $O(1)$ per iteration, you confirmed that it's $O(\log (\log(y))$. But we need to find all the powers of $2$ within the given range. $\endgroup$
    – anonuser01
    Commented Aug 16, 2021 at 4:40
  • $\begingroup$ Even with $c$, it seems that have a to do a linear scan (over the exponents), and that linear scan would seem to be $O(\log y)$ (again assuming O(1) per iteration). $\endgroup$
    – anonuser01
    Commented Aug 16, 2021 at 4:40
  • $\begingroup$ @anonuser01, oops, sorry about re-using the same variable. I changed it to $j$. $\endgroup$
    – D.W.
    Commented Aug 16, 2021 at 4:49
-1
$\begingroup$

A simple algorithms is, start from $x$, and check whether it's power of $2$ or not, then increment one by one until you get $y$, this algorithm need $\mathcal{O}(y-x)$ steps, that each steps needs to read $\mathcal{O}(\log i)$ bits. Hence the running time is $$\sum_{i=x}^{y}\mathcal{O}(1+\log i)=\mathcal{O}\left(y-x+\log \left(\frac{y!}{(x-1)!}\right)\right)\leq\mathcal{O}((y-x)\log y)$$.

So the lower bound for solving your problem is $\mathcal{\Omega}(\log y)$ .

Note that, by using Binary search idea, we can at each step increment the counter by a $2^{2^c}$ that reduce the running time to $\mathcal{O}(\log y\log\log(y-x))$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.