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

#1 polska03  Icon User is offline

  • D.I.C Regular

Reputation: 5
  • View blog
  • Posts: 297
  • 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  Icon User is offline

  • D.I.C Head

Reputation: 28
  • View blog
  • 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  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3101
  • View blog
  • Posts: 19,141
  • 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  Icon User is offline

  • D.I.C Regular

Reputation: 5
  • View blog
  • Posts: 297
  • 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  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3101
  • View blog
  • Posts: 19,141
  • 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  Icon User is offline

  • D.I.C Regular

Reputation: 5
  • View blog
  • Posts: 297
  • 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  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3101
  • View blog
  • Posts: 19,141
  • 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  Icon User is offline

  • D.I.C Regular

Reputation: 5
  • View blog
  • Posts: 297
  • 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  Icon User is offline

  • D.I.C Head

Reputation: 28
  • View blog
  • 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  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3101
  • View blog
  • Posts: 19,141
  • 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  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10477
  • View blog
  • Posts: 38,835
  • Joined: 27-December 08

Re: big o notation

Posted 14 April 2010 - 03:06 PM

View PostGalois, 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