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?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Which machine model? $\endgroup$
    – Raphael
    Mar 5, 2015 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, 2015 at 2:01
  • 1
    $\begingroup$ It still depends on the machine (model). How do VM and CPU implement shift? $\endgroup$
    – Raphael
    Mar 6, 2015 at 7:31

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ I meant in implementation in Java. Sorry for not being specific. $\endgroup$
    – Johhny Bravo
    Mar 6, 2015 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, 2015 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, 2015 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, 2015 at 14:08
  • $\begingroup$ @YuvalFilmus JVM instructions != machine instructions. $\endgroup$
    – Raphael
    Mar 6, 2015 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

Improve this answer
$\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$
    – David Richerby
    Mar 5, 2015 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, 2015 at 6:50

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.