| Re: A few questions about A1P1 |
|
 |
|
 |
|
 |
|
 |
Group: uw.cs.cs341 · Group Profile
Author: Vitalijs DitmansVitalijs 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.
*gets his notes from CS240 out*
1. Take lim f(x)/g(x) as x->inf. (L'hopitals rule is very helpful)
---- if lim=0 - then f is in o(g) --> O(f) is in O(g)
---- if lim=cont - then f is in THETA(g) --> O(f) = O(g)
---- if lim=inf - then f is in w(g) --> O(g) is in O(f)
Wiki "Big O notation" to get descriptions of all notations.
Given the example provided (O(n) is in O(n^2)) I'm sure it is easy to
build a sequence of the most obvious runtimes, and then using tests it
wouldn't be hard to fill in the "not so obvious" runtimes.
2. log^2 n is (log n)^2 - yes...
3. Use wiki for simple math properties - they are quite helpful.
| 
