Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sorry if this is a silly question but most books claim $\log n < n$ for $n \geq 1$ without providing any proof, saying it's too obvious. Could someone give me a rigorous proof? Is there some trick or method I forgot about?

share|improve this question
1  
In fact, $\log x \leq x-1$ for any $x \geq 0$. This is equivalent to the inequality $1+t \leq e^t$ for all $t \in \mathbb R$. –  Srivatsan Sep 17 '11 at 3:06
    
Hint: $e^x = 1 + x + x^2/2 + x^3/6 ... > 1 + x$ when $x>0$. –  Thomas Andrews Sep 17 '11 at 4:19
1  
See this question for proofs that for all $t\gt 0$, $\log t\leq t-1$, which implies the question you have. So this looks like a duplicate. –  Arturo Magidin Sep 17 '11 at 4:57
add comment

6 Answers

up vote 13 down vote accepted

If we let $f(n) = \log n$ and $g(n) = n$, then $f'(n) = \frac{1}{n}$ and $g'(n)=1$. Since $f(1) < g(1)$ and $f'(n) \leq g'(n)$ for $n \geq 1$, we must have $f(n) < g(n)$ for all $n \geq 1$.

The idea in the last sentence is sometimes called the racetrack principle: If $f(n)$ and $g(n)$ denote the positions of horses $f$ and $g$ at time $n$, horse $f$ starts behind horse $g$ (i.e, $f(1) < g(1)$), and at any given time horse $f$ is never faster than horse $g$ (i.e, $f'(n) \leq g'(n)$) then horse $f$ will always be behind horse $g$ (i.e, $f(n) < g(n)$ for $n \geq 1$).


OP asks for a proof of the racetrack principle.

The racetrack principle: If $f(a) < g(a)$ and $f'(n) \leq g'(n)$ for $n \geq a$, then $f(n) < g(n)$ for $n \geq a$.

Proof: Let $h(n) = f(n) - g(n)$. Then $h'(n) = f'(n) - g'(n) \leq 0$. The mean value theorem tells us that there exists some point $x \in [a,n]$ such that $$h'(x) = \frac{h(n) - h(a)}{n-a}.$$ Since we know the claim is true for $n=a$, take $n > a$. We already know $h'(x) \leq 0$, so we get $h(n) - h(a) \leq 0$, which means $f(n) - g(n) \leq f(a) - g(a) < 0$, and so $f(n) < g(n)$ for $n \geq 1$.

share|improve this answer
    
Oops - cross-posted the same thing. Sorry! –  Billy Sep 17 '11 at 3:06
    
How do I prove this general theorem? Is it possible to do using the Big-O definition? –  Mark Sep 17 '11 at 3:08
    
@Mark: I'll add a proof. –  Mike Spivey Sep 17 '11 at 3:12
    
On the account of your proof,I guess we can call it a variation of racetrack principle :-) –  Quixotic Sep 17 '11 at 3:35
add comment

How rigorous do you need? If it's rigorous enough in your context, prove that log(1) < 1 (shouldn't be hard!), and then show that the derivative of log(x) is less than or equal to the derivative of x for all $x \geq 1$.

share|improve this answer
    
Could you prove this using Big-O definition? –  Mark Sep 17 '11 at 3:16
2  
@Mark: No, this isn't what big O notation is about. Big O describes limiting behaviour (e.g. as two functions go to infinity), and says nothing about what they do elsewhere. –  Billy Sep 17 '11 at 3:18
    
You are right, but I wonder how one should prove this without using calculus. Are there more primitive tools? –  Mark Sep 17 '11 at 3:21
2  
@Mark: That depends on how you define the natural logarithm in the first place. The most direct definitions I am aware of, either as $\log x = \int_1^x dt/t$, or as the inverse of the exponential function defined as $d/dx \exp x = \exp x$ and $\exp 0 = 1$, are definitions which themselves require calculus. –  Rahul Sep 17 '11 at 3:57
add comment

just simply look at the function $f(t)=t-log(t)$. You can show that this function is always increasing and that $f(n)\ge f(1)=1$ for every $n$.

share|improve this answer
add comment

I will assume that by $\log n$ we mean the natural logarithm of $n$.

If $b > 1$, then $\log b$ is the area under the curve $y=1/x$, above the $x$-axis, from $x=1$ to $x=b$.

This area is clearly less than the area of the rectangle with base $b-1$ and height $1$, so $\log b <b-1$.

Comment: It is not uncommon in calculus courses to define $\log b$ as above, and then introduce the exponential function. If we want to make the argument rigorous, we would probably introduce the definite integral before introducing the derivative, and define $\log b$ as $\int_1^b \frac{1}{t} dt$. The inequality we need is an easy consequence of the definition of Riemann integral.

share|improve this answer
add comment

For $n\geq 1$, $\log n < n$ iff $n < e^n = 1 + n + n^2/2! + n^3/3! + \cdots$

share|improve this answer
add comment

In your comments you seem ask about this in the context of the big O notation -- e.g., the concept frequently used in computer science that when analyzing an algorithm for time (or resource consumption like RAM). In big O notation, the following order appears (with constant time as best, and exponential time being worst):

  • $O(1)$ - constant time
  • $O(\log N)$ - logarithmic
  • $O(N)$ - linear
  • $O(N \log N)$ - loglinear
  • $O(N^2)$ - quadratic (followed by other polynomial times e.g., $O(N^3)$ - cubic, etc.)
  • $O(2^N)$ - exponential time

You aren't going to come up with a mathematical proof for this ordering that shows for every $N$ that a $O(\log N)$ function will be smaller than every $O(N)$ function, because it simply isn't true. To demonstrate with a counterexample, let $f(N) = 10^{100} \log N$ (an $O(\log N)$ algorithm; you ignore the constant multiplier), and let $g(N) = N$ ($O(N)$ algorithm). While $N \lt 10^{98}$, $f$ the logarithmic function will be larger (and hence slower; less optimal) than $g$ the linear-time function, opposite to what you usually expect.

The point of big O notation is that the scaling what usually matters most is how the functional will scale for large N. Comparing any logarithmic and linear function, the logarithmic function will always be smaller than the linear function for all values of $N$ larger than some finite number. You would say that a $O(\log N)$ function grows asymptotically slower than a $O(N)$ function.

Note in many cases like comparing $f(N) = N$ and $g(N) = \log N$ it will be true over the entire domain of $N$ (equivalent to $N \gt 0$).

The power of big-O notation is that is if you know you have an $O(N)$ and an $O(\log N)$ function and both take 2 seconds to do when $N = 100$, when you need to process $N = 100000$ cases, the O(N) function will worst-case take roughly 2000 seconds, but the $O(log N)$ function will take only about 5 seconds.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.