I have a rather simple question which my own answer to it needs justification. I'm still learning about algorithmic complexity and am reading the article CRGreathouse so graciously gave me. Say I have an n-bit number and it is stored as the input in a simple computer algorithm. Next, this algorithm adds 1 to the original input to produce the output n+1. Wouldn't this operation only take 1 bit operation (as we are only manipulating 1 bit in the original input to produce the output), and hence, it would have a run-time bit-complexity of O(1)? If n=1000000, then using the algorithm proposed, the output, 1000001, would take O(1) time, right?

[QUOTE=flouran;156852]I have a rather simple question which my own answer to it needs justification. I'm still learning about algorithmic complexity and am reading the article CRGreathouse so graciously gave me. Say I have an n-bit number and it is stored as the input in a simple computer algorithm. Next, this algorithm adds 1 to the original input to produce the output n+1. Wouldn't this operation only take 1 bit operation (as we are only manipulating 1 bit in the original input to produce the output), and hence, it would have a run-time bit-complexity of O(1)? If n=1000000, then using the algorithm proposed, the output, 1000001, would take O(1) time, right?[/QUOTE]


Nope. The bit complexity is O(n). Hint: "carries". You are not "only manipulating 1 bit in the original input"

[quote=R.D. Silverman;156862]Nope. The bit complexity is O(n). Hint: "carries". You are not "only manipulating 1 bit in the original input"[/quote]
Oh, ok. I understand. Thanks. Do you know of any good books that talk about algorithmic complexity for beginners like myself (for god's sakes I can't even figure out the bit complexity of adding 1 to an n-bit integer)? I am reading one article given to me by CRGreathouse and that is rather helpful, but I was wondering if you know of any beginner texts as well.

[QUOTE=R.D. Silverman;156862]Nope. The bit complexity is O(n). Hint: "carries". You are not "only manipulating 1 bit in the original input"[/QUOTE]

This raises an interesting point, because potentially, you are manipulating n bits, but on average, you are only manipulating 2 bits. Is there a concept of bit complexity that takes "on average" into account?

[QUOTE=R.D. Silverman;156862]Nope. The bit complexity is O(n). Hint: "carries". You are not "only manipulating 1 bit in the original input"[/QUOTE]

Yes. To avoid confusing our friend, that's for adding 1 to an n-bit number, not adding 1 to n.

[QUOTE=philmoore;156864]This raises an interesting point, because potentially, you are manipulating n bits, but on average, you are only manipulating 2 bits. Is there a concept of bit complexity that takes "on average" into account?[/QUOTE]

I don't know of a concept that is exactly the same, but amortized complexity is close. The complexity of adding 1 to an n-bit number k times is O(k + n), so the amortized complexity of adding 1 to n (k => n) is O(1).

[quote=CRGreathouse;156865]Yes. To avoid confusing our friend, that's for adding 1 to an n-bit number, not adding 1 to n.[/quote]
When you say adding 1 to an n-bit number are you talking about bit-complexity, whereas if you are adding 1 to n then are you talking about algebraic complexity?

My central confusion between arithmetic complexity and bit complexity is discerning which is which. For instance, how can I figure out the bit complexity of an algorithm for n bits if I know the arithmetic complexity of the algorithm for n digits? In, [URL="http://oldweb.cecm.sfu.ca/%7Epborwein/PAPERS/P29.pdf"]http://oldweb.cecm.sfu.ca/~pborwein/PAPERS/P29.pdf[/URL], Borwein talks about the complexity of calculating the factorial for n digits. But couldn't he be referring to the bit-complexity of the factorial since a bit is a [B]b[/B]inary dig[B]it[/B]. Thus, n digits can mean n binary digits. Could someone please clarify this for me? Is Borwien talking about bit complexity or arithmetic complexity in his paper (and how can I tell that it what he is talking about since he doesn't specify)?

[QUOTE=flouran;156866]When you say adding 1 to an n-bit number are you talking about bit-complexity, whereas if you are adding 1 to n then are you talking about algebraic complexity?[/QUOTE]

Either. Do you understand the difference?

Using "n-bit number" or "n" has nothing to do with it. It has everything to do with the assumed complexity of basic operations -- arithmetic complexity gives them unit cost.

[quote=CRGreathouse;156869]Either. Do you understand the difference?

Using "n-bit number" or "n" has nothing to do with it. It has everything to do with the assumed complexity of basic operations -- arithmetic complexity gives them unit cost.[/quote]

As you can see I don't hence my most recent post,
[quote=flouran;156867]My central confusion between arithmetic complexity and bit complexity is discerning which is which. For instance, how can I figure out the bit complexity of an algorithm for n bits if I know the arithmetic complexity of the algorithm for n digits? In, [URL="http://oldweb.cecm.sfu.ca/%7Epborwein/PAPERS/P29.pdf"]http://oldweb.cecm.sfu.ca/~pborwein/PAPERS/P29.pdf[/URL], Borwein talks about the complexity of calculating the factorial for n digits. But couldn't he be referring to the bit-complexity of the factorial since a bit is a [B]b[/B]inary dig[B]it[/B]. Thus, n digits can mean n binary digits. Could someone please clarify this for me? Is Borwien talking about bit complexity or arithmetic complexity in his paper (and how can I tell that it what he is talking about since he doesn't specify)?[/quote]

By the way, what do you mean by unit cost?

[QUOTE=flouran;156872]By the way, what do you mean by unit cost?[/QUOTE]

Cost 1, without regard to the size of the numbers involved.

[quote=CRGreathouse;156889]Cost 1, without regard to the size of the numbers involved.[/quote]
Got it. So in the article I posted, Borwein is referring to the run-time [B]bit[/B]-complexity of computing the factorial for n bits, right?