Math Is Fun Forum

sak10

Member

Registered: 2010-04-26

Posts: 4

Algorithms and Big 0 Theta notation

I really need the solution to these questions

1.  Use big-O 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?
2.  Suppose f is a function that returns the result of reversing the string of symbols given as its input, and g is a function that returns the concatenation of the two strings given as its input. If x is the string hrwa, what is returned by g(f(x),x)? Explain your answer - don't just provide the result!

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Algorithms and Big 0 Theta notation

Hi sak10;

For b) why not just program it in your favorite language and try it?

This is mine:

f[s_]:=StringReverse[s]

g[s1_,s2_]:= s1<>s2

g[f["hrwa"],"hrwa"] - > "awrhhrwa"

You can see f reverses the string, g takes 2 arguments and concantenates them together.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Algorithms and Big 0 Theta notation

Hi

I recently read A Beginners’ Guide to Big O Notation and while I appreciate such efforts I don’t think it went far enough. I’m a huge fan of “plain English” explanations to, well, anything. Just look at the formal definition of Big O. The only people who can understand that already know what it means.

Bravo Bill! I hate jargon too. Try these links, this is how I think about Big O, you might get into a little trouble with his loose definition but...
Try these pages on for size, unless you run into a bunch of topologists you will be fine with this.

http://www.cforcoding.com/2009/07/plain … big-o.html

http://stackoverflow.com/questions/3255 … oximate-it

Addition the grade school way is O(n) and multiplication the grade school way is O(n^2)

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

sak10

Member

Registered: 2010-04-26

Posts: 4

Re: Algorithms and Big 0 Theta notation

Can pls give the algorithm in the second question better.

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Algorithms and Big 0 Theta notation

Hi sak10;

The algorithm for what? I am not following you. Did you look at those 2 links I provided?

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.