1
$\begingroup$

I was wondering what would be a time complexity of shifting a binary or a decimal number? For example: 0011, when I shift it left I get 0001.

I was thinking that the time complexity is $\Theta(n)$, because we have to shift every number.

I need it to calculate $m*{b^\frac{n}{2}}$, where $m$ is some number and $b$ might be 2 (in case of binary) or 10 (decimal). Therefore instead of multiplication, I just shift to multiply, and therefore complexity is $\Theta(n)$.

Am I correct or is my thinking wrong?

$\endgroup$
3
  • 2
    $\begingroup$ Which machine model? $\endgroup$
    – Raphael
    Mar 5 '15 at 19:21
  • $\begingroup$ It is not machine model - it is software: java. Where there was a shift function. Sorry for not being specific $\endgroup$ Mar 6 '15 at 2:01
  • 1
    $\begingroup$ It still depends on the machine (model). How do VM and CPU implement shift? $\endgroup$
    – Raphael
    Mar 6 '15 at 7:31
1
$\begingroup$

Time complexity is not god-given but is rather defined by the model of computation. To take a simple example, what is the time complexity needed for adding two numbers? In the RAM machine model, this operations takes constant time, as long as the numbers are not "too big". The rationale is that modern hardware implements addition as a fast machine instruction; if the numbers are not "too big" then they fit into single registers. The same reasoning holds for shifts. You have to be careful, however, that the size of the relevant quantities doesn't blow up.

$\endgroup$
6
  • $\begingroup$ I meant in implementation in Java. Sorry for not being specific. $\endgroup$ Mar 6 '15 at 2:00
  • 1
    $\begingroup$ I assume the Java virtual machine has a shift instruction, so shifting takes constant time. $\endgroup$ Mar 6 '15 at 2:10
  • $\begingroup$ @YuvalFilmus Some language having an instruction is little proof that instruction taking constant time. (Even though most low-level languages seem to be built that way.) $\endgroup$
    – Raphael
    Mar 6 '15 at 7:31
  • $\begingroup$ @Raphael The concept of "constant time" is artificial. You have to define it. Assuming that your goal is to predict the running time of programs, it seems safe to assign constant time to "machine instructions". $\endgroup$ Mar 6 '15 at 14:08
  • $\begingroup$ @YuvalFilmus JVM instructions != machine instructions. $\endgroup$
    – Raphael
    Mar 6 '15 at 17:46
-2
$\begingroup$

O(n) and CPU execute in one Register then put the result to another Register, so the performance is quick.

Reference http://chortle.ccsu.edu/assemblytutorial/Chapter-12/ass12_2.html

$\endgroup$
2
  • 1
    $\begingroup$ $O(n)$ with respect to what machine model? How many bits are in your CPU register? What happens if you want to shift more bits than that? $\endgroup$ Mar 5 '15 at 20:29
  • $\begingroup$ Because of algorithm, shift left/right is clearly O(n) for all machine model. How you do it faster without enumerating all bits. Except you use electric signal. CPU Register's bit length depends on CPU model or Instruction set. (For example: x86_64 has 64-bit register,Intel 8086 has 16-bit register) Shifting more bit than Register length causes zero-bit will be padding, I have experience in shift operator $\endgroup$
    – Ronaldinho
    Mar 6 '15 at 6:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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