A few questions about A1P1

POPULAR GROUPS

more...

uw.cs.cs341 Profile…

A few questions about A1P1

Author: Lyle Waldman
Date: Sep 16, 2008 22:07

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

3 Comments

Re: A few questions about A1P1

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 ...

Show full article (1.37Kb)

no comments

Re: A few questions about A1P1

Author: Vitalijs Ditmans
Date: Sep 18, 2008 19:09

>> 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?
>>
>>

> 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) )

undefined limits (limit doesn't exist) can't happen in our scenarios,
since all functions are monotonically increasing functions. And when
limit is undefined (Example cos(x) and sin(x)) then we can't order these
2 functions in a sequence, since neither function contains the other.

Show full article (1.50Kb)

no comments

Re: A few questions about A1P1

Author: Anna Lubiw
Date: Sep 22, 2008 12:28

In article ,
Lyle Waldman wrote:

Yes, you will find this in [CLRS, section 3.1]. You can use material
from the text for your assignments. (But don't just say "page x in CLRS",
explain things yourself.)

>2) What is (log^2)n? I'm presuming it's (logn)^2.

Yes, that's right.

>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?

Appendix A of [CLRS] has some useful things.

Anna Lubiw

no comments