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?????

# big o notation

Page 1 of 1## 10 Replies - 5329 Views - Last Post: 14 April 2010 - 03:06 PM

##
**Replies To:** big o notation

### #2

## Re: big o notation

Posted 14 April 2010 - 01:54 PM

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

### #3

## Re: big o notation

Posted 14 April 2010 - 01:57 PM

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

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

### #4

## Re: big o notation

Posted 14 April 2010 - 02:27 PM

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

### #5

## Re: big o notation

Posted 14 April 2010 - 02:29 PM

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

55

+55

--2 digits, 2 additions

Now try your hand at multiplication

### #6

## Re: big o notation

Posted 14 April 2010 - 02:31 PM

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

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

### #7

## Re: big o notation

Posted 14 April 2010 - 02:34 PM

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.

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

### #8

## Re: big o notation

Posted 14 April 2010 - 02:37 PM

okay I think that makes sense, so additons=n

and multiplication is equall to (ex 55x55=4, 555x555=9) so N^2 for multiplication?

and multiplication is equall to (ex 55x55=4, 555x555=9) so N^2 for multiplication?

### #9

## Re: big o notation

Posted 14 April 2010 - 02:40 PM

@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.

@Polska: The last one is right.

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

### #10

## Re: big o notation

Posted 14 April 2010 - 02:53 PM

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.

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

### #11

## Re: big o notation

Posted 14 April 2010 - 03:06 PM

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.

Page 1 of 1