# big o notation

Page 1 of 1

## 10 Replies - 5372 Views - Last Post: 14 April 2010 - 03:06 PM

### #1 polska03

• D.I.C Regular

Reputation: 5
• Posts: 302
• Joined: 28-November 09

# big o notation

Posted 14 April 2010 - 01:48 PM

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?????
Is This A Good Question/Topic? 0

## Replies To: big o notation

### #2 Galois

• D.I.C Head

Reputation: 28
• Posts: 207
• Joined: 27-March 10

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

Was This Post Helpful? 0

### #3 KYA

• Wubba lubba dub dub!

Reputation: 3179
• Posts: 19,210
• Joined: 14-September 07

## 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
Was This Post Helpful? 0

### #4 polska03

• D.I.C Regular

Reputation: 5
• Posts: 302
• Joined: 28-November 09

## 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?
Was This Post Helpful? 0

### #5 KYA

• Wubba lubba dub dub!

Reputation: 3179
• Posts: 19,210
• Joined: 14-September 07

## 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
Was This Post Helpful? 0

### #6 polska03

• D.I.C Regular

Reputation: 5
• Posts: 302
• Joined: 28-November 09

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

Was This Post Helpful? 0

### #7 KYA

• Wubba lubba dub dub!

Reputation: 3179
• Posts: 19,210
• Joined: 14-September 07

## 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.
Was This Post Helpful? 1

### #8 polska03

• D.I.C Regular

Reputation: 5
• Posts: 302
• Joined: 28-November 09

## 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?
Was This Post Helpful? 0

### #9 Galois

• D.I.C Head

Reputation: 28
• Posts: 207
• Joined: 27-March 10

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

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

Was This Post Helpful? 2

### #10 KYA

• Wubba lubba dub dub!

Reputation: 3179
• Posts: 19,210
• Joined: 14-September 07

## 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.
Was This Post Helpful? 0

### #11 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11758
• Posts: 44,173
• Joined: 27-December 08

## 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.
Was This Post Helpful? 0

Page 1 of 1

 .related ul{list-style-type:circle;font-size:12px;font-weight:bold;}.related li{margin-bottom:5px;background-position:left 7px!important;margin-left:-35px;}.related h2{font-size:18px;font-weight:bold;}.related a{color:blue;}