[polska03]

Use big-theta notation to classify the traditional grade school algorithms for addition and multiplication. That is, if asked to add two numbers each having n-digits, how many individual additions must be performed? If asked to multiply two n-digit numbers, how many individual multiplications are required?

This is question out of my homework addignment. Would the answer simply be just n^2, where n is the number of digits?????

[Galois]

Is the answer for both questions n^2? No. Their answers are different. Picture each process and how it depends on the number of digits, it couldn't be simpler.

This post has been edited by Galois: 14 April 2010 - 01:55 PM

[KYA]

This isn't a big O question. It makes the assumption that one addition or multiplication takes up a cycle. Big O is used for growth rates.

Anyhoo, back on topic:


100 + 100

Write it like this
100
+100
----

How many additions? Do a few more


Multiplication:

55 * 66

55
x 66
----

so on and so forth


edited to correct digits

[polska03]

is it n+1 for addition and n+2 for multiplication, where n is the number of digits?

[KYA]

I misread, if they have the same digits, then it's less complicated. Same # of digits for addition is 'n' additions, each index lines up:

55
+55
--2 digits, 2 additions


Now try your hand at multiplication

[polska03]

isnt 55+55=3 additions, including the carry(2+5+5)

This post has been edited by polska03: 14 April 2010 - 02:33 PM

[KYA]

Hmmm, you need to clarify the assignment then.

1+5+5 = 1 addition, at least from how I'm looking at it. It's one operation.

[polska03]

okay I think that makes sense, so additons=n
and multiplication is equall to (ex 55x55=4, 555x555=9) so N^2 for multiplication?

[Galois]

@KYA: There's no notion of computer cycle in Big O. That's the whole point of using it - it's independent of computer architectures and hardware. So you can define function in any way you want and apply Big O to it. In this case the 2 functions take number of digits N, and return the number of digit additions and multiplications respectively.

@Polska: The last one is right.

This post has been edited by Galois: 14 April 2010 - 02:41 PM

[KYA]

Poor wordage on my part then.


The assignment gives the notion that arithmetic would take more then one iteration (a la cycle). I read too much into it.

[macosxnerd101]

Galois, on 14 April 2010 - 05:40 PM, said:

@KYA: There's no notion of computer cycle in Big O. That's the whole point of using it - it's independent of computer architectures and hardware. So you can define function in any way you want and apply Big O to it...

For these reasons, operations defined by the language (like addition, subtraction, multiplication, division, modulus, etc.) are assumed to take a constant 1 step for the purpose of efficiency analysis.