Big O notation complexity for binary multiplcation [closed]

Question

Closed. This question needs details or clarity. It is not currently accepting answers.

---

Want to improve this question? Add details and clarify the problem by editing this post.

Closed 8 years ago.

Improve this question

What is the Big O notation for the following operations:

A = 1*(1 0 1 0) + 0*(0 1 0 1)

---

Thank you OlivierLi. So, please what about this : A = 1*(0 1 1 0 1 0 1 0) + 0*(1 0 0 0 0 1 0 1) + 1 * (1 1 0 0 1 1 0 0) + 0 * (1 0 1 0 1 0 1 0). It is also O(1). As you see it is like one binary bit multiplied by 8 binary bits four times. If it is also O (1), please and kindly, How can I prove that. Thank you with best regards.

Answer 1

This is O(1).

It doesn't depend on any input at all and is always constant.

Answer 2

The problem here is, whether we assume the count of bits as a variable or as a constant.

Constant count of bits: the complexity is O(1), because the complexity is the same for all possible input numbers.

Variable count of bits: for each bit of first number you add the shifted second number. Considering that addition with arbitrary long numbers may have complexity O(N), the final complexity is O(N^2), where N is the count of bits.