Big O: 2 Functions Map from N to N+
From: Scott Turner Date: Sat, 22 Jun 1996 13:39:17 -0400 (EDT) Subject: The Big O True or False: Let f, g: N -> N+, then either f(x) is O(g(x)) or g(x) is O(f(x)). Why?
Date: Mon, 24 Jun 1996 14:17:53 -0400 (EDT) From: "Dr. Math" Subject: Re: The Big O Maybe I don't understand the question, since I don't know what you mean by "N+". If it just means positive integers, then your statement is false: f(odd number n) = 1 f(even number n) = 2^n g(odd number n) = 2^n g(even number n) = 1 But maybe "f, g: N -> N+" means increasing functions or something. Please clarify. -Doctor Tom, The Math Forum Check out our web site! http://mathforum.org/dr.math/
Date: Tue, 25 Jun 1996 09:53:01 -0400 (EDT) From: Scott Turner Subject: Re: The Big O I do mean positive integers by N+ but don't understand your explanation. If two functions map from N to N+, I picture two graphs in the upper right quadrant and it seems that if the two graphs are equal then they are O to each other, if they aren't equal, one is big O of the other? Thanks. ST
Date: Tue, 25 Jun 1996 16:56:49 -0400 (EDT) From: "Dr. Math" Subject: Re: The Big O The "O" or "big-O" notation is usually used to compare rates of growth of functions. It's used to compare what happens "in the long run", usually for functions that are both increasing, but at different rates. For applications like computer science, they are used to compare algorithm performance. For example, if you have two sorting schemes, one of which takes 1000*n*log(n) cycles to do the sort and another of which takes n^2 cycles, for sorting small numbers of items, the n^2 sort is better. In the long run, for giant sorts, the 1000*n*log(n) algorithm is better, and it's better for ALL sorting problems above a certain size. But arbitrary functions that can go up and down may not be comparable. Sometimes one is bigger and sometimes the other. The example I gave shows two functions that alternate which one is bigger forever, and not only that, but the relative size of each against the other at alternate points also grows without bound. Just because you can write down a definiton of a relationship between 2 mathematical things that sounds sort of like a comparison relationship doesn't mean that any two things can be compared. O is a comparison operator, and for some functions f and g we can say that f = O(g) or vice-versa. But there exist f and g (as in my example - and there are an infinite number of other examples) where neither f = O(g) or g = O(f) holds. -Doctor Tom, The Math Forum Check out our web site! http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.