| Re: A few questions about A1P1 |
|
 |
|
 |
|
 |
|
 |
Group: uw.cs.cs341 · Group Profile
Author: MyFavouriteJavaMyFavouriteJava Date: Sep 17, 2008 06:25
On Sep 17, 1:07Â pm, Lyle Waldman wrote:
> 1) I seem to remember from CS240 that there was a definition of Big-O
> that used limits. Â I don't have my CS240 notes on me, and I forgot the
> definition. Â I think it was something like f is O(g) if lim_n->inf(f/g)
> <= 1, which I think makes intuitive sense. Â I'm not sure though. Â Does
> anyone have these? Â They look to be really useful.
>
> 2) What is (log^2)n? Â I'm presuming it's (logn)^2.
>
> 3) Since I haven't touched Math138 for over a year (and barely touched
> it even when I was taking it), I've completely forgotten my sequences
> and series. Â Does anyone know the rule about the series n^k for k from 1
> to inf? Â It was something like n < 0 -> series converges, but was there
> any more to it?
>
> Thanks. Â If I've said too much about any of the solutions, feel free to
> moderate me, as I'm kinda getting back into the swing of newsgroups, and
> never really used one for a non-programming course...
>
> Lyle
1. YES. I think you are right. If you want to prove f(x) is NOT
O(g(x)), then you could simply take the lim f/g as x -> infinity. If
the limit does not exist, then you could say that your claim is
correct.
2. (log^2)n IS ( log(n) * log(n) )
3. I don't know neither since MATH138 is not one of my favorite course
here. :) Does anyone else know the answer? Thanks.
|