Recent content by zcd

The circular reasoning lies in the fact that you assumed your proposition is true before proceeding to prove it is true.

That's the gist of it. If you really wanted to be rigorous, l'hopital's rule can't be applied to functions of integers (it's a calculus result) so define functions f,g:\mathbb{R}\to\mathbb{R}\quad\text{as}\quad f(x)=x^w,g(x)=\ln(x) and then apply l'hopital's rule. Since the integers are a...

That's not necessarily true either. The statement n^w ∈ O(ln(n)) is equivalent to "∃c,N>0 such that ∀n>N, n^w< c*ln(n)". Since this is false, we can only assume its negation, which is "∀c,N>0 ∃n>N, n^w>= c*ln(n)". This is not the same as saying n^w always outgrows against ln(n); it only says...

There's a subtle difference here. What I proved was that any positive power is not in O(log n), or that log n doesn't provide an upper bound to power functions. It does not necessarily immediately imply that any power function gives an upper bound for log(n).

You did the limit incorrectly; here's a (counter) proof of a similar claim to help you get started: If we start by assuming (for contradiction) that n^w\in O(\ln(n)) for some w>0, then there exist c,N>0 such that c\ln(n)\geq n^w for all n>N, or equivalently...

You can try to prove the first claim with the same method as before: \lim_{n\to\infty}\frac{\log(n)}{n^w} for some w>0. The base of the log doesn't matter, so working with the natural log will make it easier.

You didn't choose n large enough. The power n^(.01) will win against log(n), but will take much longer. If you solve for their intersections, the larger intersection when the power term wins against log_2(n) is around 7*10^(299) http://www.wolframalpha.com/input/?i=n%5E%28.01%29%3Dlog_2+n Be...

My mistake, I meant to say f(n) ∈ O(g(n)) in my previous post. Your n isn't large enough, try comparing 10^100 vs 10^1000.

If f(n) ∈ Ω(g(n)), then you already know that the log term does not in fact win against the power term in growth. It may feel counterintuitive because g(n) has the power term as well, but if the log term insignificant in comparison then you're really only comparing the powers.

Try taking the limit of the ratio \frac{f(n)}{g(n)}. If the limit converges, you use the result to get a relationship between the two.

1. Homework Statement [/b] You are given the following pieces of information about a real, stable, discrete-time signal x and its DTFT X, which can be written in the form X(\omega)=A(\omega)e^{i\theta_x(\omega)} where A(\omega)=\pm|X(\omega|. a) x is a finite-length signal b) \hat{X} has...

Homework Statement You are given the following pieces of information about a real, stable, discrete-time signal x and its DTFT X, which can be written in the form X(\omega)=A(\omega)e^{i\theta_x(\omega)} where A(\omega)=\pm|X(\omega|. a) x is a finite-length signal b) \hat{X} has exactly two...

Flowers for Algernon, the book from which the movie was adapted, was a great read.

There will always be an elderly population, and that elderly population will always need medication.

You could confirm what you wrote: (\frac{1}{n+1})( \frac{2}{n+1} ) ...( \frac{n-1}{n+1} )( \frac{n}{n+1} )< 1 \Rightarrow n! < (n+1)^n