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$
  • 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$ – Johhny Bravo 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$
  • $\begingroup$ I meant in implementation in Java. Sorry for not being specific. $\endgroup$ – Johhny Bravo Mar 6 '15 at 2:00
  • 1
    $\begingroup$ I assume the Java virtual machine has a shift instruction, so shifting takes constant time. $\endgroup$ – Yuval Filmus 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$ – Yuval Filmus 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$
  • 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$ – David Richerby 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.