Post feed
 Comments feed

Monday, November 5, 2007

Seeing you believing

Archiving things is good. Here's question 1. I highlighted the two marks at the end to indicate that I never got to that bit. Part f was interesting; I had to resort to L'Hopital's rule, to my disgust.

10 comments:

Bruce Hoult said...

Do I sense a power struggle in that bubble?

Now I'll read the post ;-)

Bruce Hoult said...

I'm not quite sure what big O notation means in this academic field, but I'm wondering whether something as simple as f(x) = 2x for x <= 0, f(x) = x for x > 0 would do the trick?

Gael said...

That will work beautifully. Give me a few hours to TeX up a proof, and I'll post it.

It took me about 20 minutes to work out that that function works though, so I would never have had time for it during the exam.

BTW, the name of the song is not Bubble.

Bruce Hoult said...

Yeah but there weren't several bubbles on you test question ;-)

And you didn't have to prove that answer I think, only state it.

Sooo .. the big O thing is basically a more general form of continuity? Simple continuity is O(1) or something like that?

Gael said...

Come on, this is 300-level. Of course we had to prove it.

And no, big O has very little to do with continuity. Nothing, in fact, except that the definitions look a bit similar.

Bruce Hoult said...

Urg, right, I'm dumb. Having now looked at the definition (a/t Wolfram anyway) it's deliberately ignoring the small picture in order to look at the big picture. I was a little surprised to see the absolute value thing in there, but it makes sense -- we don't have to deal with negative numbers in the things we use big O for in computers.

So, so you use it for thinking about limits, or for smoothing things, or something else?

I'm not sure whether this is a definition difference (in us allowing an additive constant as well as a multiplicative one) or just us being sloppy, but I think that we computer scientists would say that something like f(x) = x^2 + sin(x) was O(x^2) whereas if it understand it correctly you would not.

Similarly if you have f(x) = sin(x) + cos(x+5)/100, we'd all agree that it was O(1), but I think computer types might also in some way find it useful to call that O(sin(x)) even though you mathematicians would not. i.e. to us it's more about a simple matter of dropping small terms off and looking at what happens overall, or at infinity, than on peering too closely at zero crossings.

p.s. was "power struggle" not a valid answer?

Gael said...

You computer scientists do absolutely disgusting things with Landau's notation. Chris would call you applied mathematicians if he saw you doing it.

That's not to say that any of your examples here are invalid, I haven't really thought about them yet.

Wolfram's definition of little o is unsatisfactory by virtue of being insufficiently general. Their big O is more or less okay conceptually, but it's not absolutely accurate [by comparison with Chris's lecture notes].

I've defined big O properly in the proof which I'll post later [blogger's upload is broken for now].

And no, "power struggle" was not a valid answer because it's not the title of the song!

Bruce Hoult said...

I wonder if what we're doing with something like f(x) = x^2 + sin(x) is saying that that is O(x^2) + O(1) and then in a separate step saying that we don't care about the O(1).

A more realistic example is that we might be adding up the operations in, say, sorting an array, and find that the number of operations (or the number of CPU clock cycles) is something like, say...

0.5*n^2 + 10*n + 7

.. and so we say that's O(n^2) + O(n) + O(1) (which I think you and Chris would agree with) and then in a totally different step we say that we only care about the O(n^2).

Just as a matter of amusement, what is the title of this song?

http://www.lyricsdepot.com/system-of-a-down/power-struggle.html

Gael said...

Jesus H. I knew lyrics sites were stupid, but I never thought they could possibly be that n00bily. Did you try any others? Never even start to believe what a lyrics site tells you until you've corroborated it.

Track listings are far more reliable.

Gael said...

Proof is now posted.

Post a Comment

You can use $\LaTeX$ here if you like. Enclose it in "$" or "\[" as if you were using your favourite editor.

Note: Only a member of this blog may post a comment.