big o notation
Page 1 of 110 Replies  4861 Views  Last Post: 14 April 2010  03:06 PM
#1
big o notation
Posted 14 April 2010  01:48 PM
This is question out of my homework addignment. Would the answer simply be just n^2, where n is the number of digits?????
Replies To: big o notation
#2
Re: big o notation
Posted 14 April 2010  01:54 PM
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
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
#5
Re: big o notation
Posted 14 April 2010  02:29 PM
55
+55
2 digits, 2 additions
Now try your hand at multiplication
#6
Re: big o notation
Posted 14 April 2010  02:31 PM
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
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
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
@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
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:
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.
