F
F
F582021-07-23 20:47:51
Algorithms
F58, 2021-07-23 20:47:51

What is the time complexity of copying a bitset?

Suppose we have two bitsets of size N. I want to transfer all values ​​from one bitset to another. What will be the time complexity of this operation?

Answer the question

In order to leave comments, you need to log in

1 answer(s)
G
Griboks, 2021-07-24
@F58

This is very language, processor, and memory dependent. If we consider a classical Turing machine, then copying one bit takes the time of reading + writing + shifting * shifting addresses => k*N.
If we consider memory cells as m bits in one, then k*N÷m=p*N.
If we copy bits in the language through a shift, then the first option is even slower.

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question