Re: A few questions about A1P1
  Home FAQ Contact Sign in
uw.cs.cs341 only
 
Advanced search
POPULAR GROUPS

more...

 Up
Re: A few questions about A1P1         

Group: uw.cs.cs341 · Group Profile
Author: MyFavouriteJava
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.
no comments
diggit! del.icio.us! reddit!