0

There is a loop which perform a brute-force algorithm to calculate 5 * 3 without using arithmetical operators.

I just need to add Five 3times so that it takes O(3) which is O(y) if inputs are x * y. However, in a book, it says it takes O(2^n) where n is the number of bits in the input. I don't understand why it use O(2^n) to represent it O(y). Is it more good way to show time complexity?. Could you please explain me?

I'm not asking other algorithm to calculate this. 

int result = 0
for(int i=0; i<3; i++){
    result += 5
}
devDNA
  • 133
  • 6
  • 3
    The runtime is a constant (O(1)) since this loop's runtime doesn't depend on any external parameters. Is this literally what the book says? Can you cite the specific wording and what it refers to? – templatetypedef Aug 06 '17 at 22:06
  • you are talking about "numer of bits in the input" I highly suspect you are leaving out some very relevant information about what the book says. – bolov Aug 06 '17 at 22:09
  • In a book, it says "to form 5x3, we would start with 0 and repeatedly add 5. The time complexity is very high as much as O(2^n), where n is the number of bits in the input". But 3 is 0011. what does it mean n is the number of bits? In order to represent 3, it only needs 2 bits. O(2^2) = O(4). Why the writer uses O(2^n), which n is the number of bits in the input, instead of O(n) ? – devDNA Aug 06 '17 at 22:10
  • @DannaDChoe oh, my bad then. Throw the book. Or there is some context we are not aware of. – bolov Aug 06 '17 at 22:11
  • @DannaDChoe That would be if the loop was dependant upon the number of bits, but it's constant here; it will run 3 times regardless. Even if it was dependent on the number of bits, I would expect linear runtime, not 2^n. – Carcigenicate Aug 06 '17 at 22:12
  • That claim from the book makes no sense - either the book is very poorly written or this is part of a larger example. What book is this? – templatetypedef Aug 06 '17 at 22:13
  • @templatetypedef https://books.google.ca/books?id=y6FLBQAAQBAJ&lpg=PA51&ots=AtHocOA8rk&dq=%22we%20would%20start%20with%200%20and%20repeatedly%20add%205%22%20%22where%20n%20is%20the%20number%20of%20bits%20in%20the%20input%22&pg=PA51#v=onepage&q=%22we%20would%20start%20with%200%20and%20repeatedly%20add%205%22%20%22where%20n%20is%20the%20number%20of%20bits%20in%20the%20input%22&f=false – Ry- Aug 06 '17 at 22:17

3 Answers3

3

You’re claiming that the time complexity is O(y) on the input, and the book is claiming that the time complexity is O(2n) on the number of bits in the input. Good news: you’re both right! If a number y can be represented by n bits, y is at most 2n − 1.

Ry-
  • 218,210
  • 55
  • 464
  • 476
1

I think that you're misreading the passage from the book.

When the book is talking about the algorithm for computing the product of two numbers, it uses the example of multiplying 3 × 5 as a concrete instance of the more general idea of computing x × y by adding y + y + ... + y, x total times. It's not claiming that the specific algorithm "add 5 + 5 + 5" runs in time O(2n). Instead, think about this algorithm:

int total = 0;
for (int i = 0; i < x; i++) {
    total += y;
}

The runtime of this algorithm is O(x). If you measure the runtime as a function of the number of bits n in the number x - as is suggested by the book - then the runtime is O(2n), since to represent the number x you need O(log n) bits. This is the distinction between polynomial time and pseudopolynomial time, and the reason the book then goes on to describe a better algorithm for solving this problem is so that the runtime ends up being a polynomial in the number of bits used to represent the input rather than in the numeric value of the numbers. The exposition about grade-school multiplication and addition is there to help you get a better sense for the difference between these two quantities.

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
  • Thank you for your answer. I have used the numeric value to represent time complexity unlike the book. Hum.. Should I have to use the number of bits used to represent number for the time complexity? – devDNA Aug 06 '17 at 22:26
  • It depends on context. It's never a bad idea to have the distinction in the back of your head, especially if you're working with inputs that can be arbitrarily large. – templatetypedef Aug 06 '17 at 22:28
  • ah. okay. Thanks for your time and help. – devDNA Aug 06 '17 at 22:56
0

Do not think with 3 and 5. Think how to calculate 2 billion x 2 billion (roughly 2^31 multiplied with 2^31)

Your inputs are 31 bits each (N) and your loop will be executed 2 billion times i.e. 2^N.

So, book is correct. For 5x3 case, 3 is 2 bits. So it is complexity is O(2^2). Again correct.

xycf7
  • 913
  • 5
  • 10
  • Ya. I know the given runtime is also correct, but I just wanted to know why it use O(2^n) to represent it O(y). Is it more good way to show time complexity? – devDNA Aug 06 '17 at 22:20
  • basically yes. it is a better way to show complexity. let me elaborate a little more: initial complexity analysis started on turing machies (with tape inputs) and since the states were constant, complexity mostly depended on the length of the input. And input could be in any base (base 2, base 10, base 36 etc.) But analysis are done in the base 2 representations of the inputs, so complexity numbers between different machines/algorithms could be comparable. And modern computers are also built on binary systems, using binary almost everywhere makes more sense. – xycf7 Aug 06 '17 at 22:29