13

Let's say I have a linear function f(n)= an+b, what is the best way to prove that this function belongs to O(n2) and Θ(n)?

I do not need mathematical rigor here. I need a programmers answer. Some logical way of explaining.

This is precisely why I didn't post the question in mathematics Q&A and instead in the Programmers Q&A.

gnat
  • 21,442
  • 29
  • 112
  • 288
Geek
  • 5,107
  • 8
  • 40
  • 58
  • Why would a function belong to O(n^2)? – NoChance Jul 28 '12 at 09:43
  • 2
    @EmmadKareem In literature often the Big O notation is often used casually to represent tight bounds which is basically Θ(n) . Big O is the upper bound actually . – Geek Jul 28 '12 at 09:51
  • A linear function is of order O(n) and the upper bound of O(n) is not n*n. – NoChance Jul 28 '12 at 09:55
  • 1
    @EmmadKareem "upper bound of O(n) is not n*n. " ,,there is no upper bound of O(n). O(n) itself defines the upper bound . It can actually contain a set of functions that satisfy the condition : f(x) ∈ O(g(x)) as there exists c > 0 (e.g. c = 1) and x0 (e.g. x0 = 5) such that f(x) < cg(x) whenever x > x0. – Geek Jul 28 '12 at 10:13
  • You want to prove that a linear function belongs to O(n*n) - Tom me this does not sound logical. – NoChance Jul 28 '12 at 10:20
  • 2
    @EmmadKareem Actually O(n) \subset O(n^2) \subset O(n^3) and so on, thus f \in O(n^2) by transitivity of \subset. Note that \subset is not \subseteq. – scarfridge Jul 28 '12 at 10:21
  • @scarfridge, so it is sufficient to prove that it belongs to O(n) and the requirement that it belongs to O(n*n) is redundant. – NoChance Jul 28 '12 at 10:23
  • @EmmadKareem Yes, but OP talks about \Theta(n) and thus it needs to be shown that f \in o(n) and f \in O(n). – scarfridge Jul 28 '12 at 10:25
  • 6
    "I need a programmers answer. Some logical way of explaining." - well how do you define "logical"? Math is logical. Anything less than rigorous thinking is ***wrong*** here. You can try explaining the topic, but without digesting the (otherwise not hard) math behind it you won't actually get it - you'll only have a foggy sense of what it means. – Tamás Szelei Jul 28 '12 at 11:42
  • @fish I see what you are saying but why I said I do not not require much maths is because this I didn't post in the http://mathematica.stackexchange.com/ forum. I too strongly feel about the maths part like you do but thought it wasn't necessary for this case , though . – Geek Jul 28 '12 at 12:17
  • 2
    @Geek: I guess you mean [math.SE]? [cs.SE](http://cs.stackexchange.com) would also be a good address. – Raphael Jul 28 '12 at 16:27

3 Answers3

20

The Big Oh notation (O, Theta, Omega) is about growth rates of functions.

When you implement an algorithm, it has a certain characteristic how the runtime changes when you increase the dataset operates on. Now, you may optimize the algorithm so it runs faster by a factor of 100. Sure, this is great, but essentially, it's still the same algorithm. Similarly, in a few years, computers may be twice as fast as they are today.

The Landau notation abstracts away these constant factors. It doesn't care about whether an algorithm f is always twice as fast as another algorithm g: Maybe g can be optimized to run 4 times faster, or you might be able to buy faster hardware instead. If you look at it from this perspective, you might say they are "the same". (That is not to say you can (always) ignore constant factors in practice.)

Big oh specifies an upper bound, it's similar to the <= relation.

You will agree that 1 < 2 is true. Does that mean that 1 cannot be less than any other number? Certainly not. There is an infinite amount of numbers that are bigger than 1.

With growth rates, it's similar. O(n) denotes the set of all functions, that grow linearly (or more slowly). O(n^2) on the other hand denotes all those functions, that grow with quadratic compelxity (or slower). I am sure that you will agree that a linear function grows more slowly than a quadratic function.

This is why a function can be in more than one "Big-oh" class.

Here is a comparison of different functions with constraints: (from Knuth's Concrete mathematics)

growth rate comparisons

From left to right, functions grow faster.

Also, enter image description here, meaning n^2 grows faster than n^1 because 2 > 1.

Definitions

definition Omega

"f grows faster or equally fast as g"

definition big Oh

"f grows slower or equally fast as g"

definition Theta

The combination of the above two. It says the function f grows "equally fast" as g. It's an equivalence relation.

Interpretation

Let's say you have two algorithms, f and g.

Omega

Assuming f not in Theta of g, f in Omega of g means that no matter your budget, there is no constant amount of computing power that you can add to your system, such that f will always run as fast as g.

Big oh

Assuming f not in Theta of g, f in Big Oh of g means that if you have enough data, f will always run faster than g, no matter how much computing power you add to your system.

Proof

If you are really trying to prove this, you need to show using the definitions of the Landau notation that your function satisfies the necessary conditions.

So you need to find values for c, d, n_0 such that the condition holds.

Here is how you can do that for the lower bound with c:

proof

It is important to realize, that me arbitrarily defining c as being smaller than a-1 is perfectly fine. The definition of Theta(g) says that "there exists a c". It can be any value as long as it is bigger than 0. (If a is a positive real number, you would need to change the proof slightly however, because a - 1 might actually be negative)

(I am assuming a to be positive, otherwise the function will always be negative for big values of n, which makes no sense for a function denoting the runtime.)

You can try doing it for the upper bound, it's quite similar. If you don't know how, I can provide a proof for you.

Hint: start with d > a + 1

Attention

It is important that you do not prove it the wrong way around. If you assume that (an + b) is in O(n) and go from there, you have not proven what you wanted. You will need to verify that all of your steps go both way, i.e. instead of => you have <=>.

phant0m
  • 2,614
  • 16
  • 25
  • 2
    That's it. Too bad people freak out because of the math, it is very simple actually. – Tamás Szelei Jul 28 '12 at 11:43
  • question states: "I do not need mathematical rigor here. I need a programmers answer..." [Notation](http://en.wikipedia.org/wiki/Function_%28mathematics%29#Notation) used in this answer does not look like a good fit for the question – gnat Jul 28 '12 at 11:45
  • 1
    @gnat Hmm, I thought the question said "prove" at one point. Anyway, I have added interpretations for the mathematical definitions. – phant0m Jul 28 '12 at 11:46
  • @phant0m great answer . exactly what i was looking for . The maths in the answer made it more solid , even though "maths" was not specifically asked for in the original question. Thanks a ton. – Geek Jul 28 '12 at 12:07
  • @Geek, I'm glad you like it. If you have any more questions, feel free to ask and I can clarify/expand my answer. – phant0m Jul 28 '12 at 12:14
5

When you're dealing with polynomials, you only care about the degree of the polynomial. That is, for an + b, you only care about n. If it was an^3 + bn^2 + cn + d, you would only care about n^3.

So a polynomial with degree d will always be in Θ(n^d). Simple.

Now we need to talk about the difference between Θ and O. Essentially, it's the same difference as between == and <= respectively. So Θ(n) means that it is always within a constant factor of n. O(n) means that it is always either within a constant factor of n or less than n.

This means that any function in Θ(s), for any s, will also be in O(s). Also, if a function is in Θ(s) and s is always less than some other function t, that function is in O(t) but not Θ(t).

For the sake of completeness, there is also Ω(n). If Θ represents == and O represents <=, Ω represents >=. So an + b is in Ω(1), Θ(n) and O(n^2).

As I said earlier, it's really easy to figure out what class polynomials are in--you just look at the degree. There are some other functions that are easy to work with as well.

Any functions in the form of a^bn for arbitrary a and b are in Θ(a^n). For any value c >= a, they are in O(c^n). Every polynomial is in O(2^n). Essentially this just says that exponential functions always beat out polynomials and that the base of the exponential function matters.

Logarithms are the opposite. For one, log_b n is in Θ(log n) for any b. This means the base doesn't matter for logarithms. This makes sense because switching between different bases in logarithms is just multiplying by a constant. Logarithmic functions are also in O(n)--that is, a logarithmic function is smaller than any polynomial (at least of degree 1).

Given a sum of these functions, the biggest one "wins". So n + log n is in Θ(n) because the n term dominates the log n term. Multiplication is more complicated. For CS, the only thing you need to know is that nlog n is between n and n^2.

Tikhon Jelvis
  • 5,206
  • 1
  • 24
  • 20
  • 1
    pretty good. Per my recollection above explanation is as close to classical [Algorithm Design Manual](http://www.algorist.com/ "what's this?") as it gets – gnat Jul 28 '12 at 10:46
  • 1
    @Tikhlon nice write up.So +1. But the one that I accepted was even better . – Geek Jul 28 '12 at 12:11
-2

Without using much math, you take the function f(n)= an+b and drop all the constants, so it looks like this f(n)= n, then you take the "n" with the highest degree as your answer Q.E.D Θ(n)

winner3000
  • 27
  • 2