Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I am a programmer and have just started reading Algorithms. I am not completely convinced with the notations namely Bog Oh, Big Omega and Big Theta. The reason is by definition of Big Oh, it states that there should be a function g(x) such that it is always greater than or equal to f(x). Or f(x) <= c.n for all values of n >n0.

Why don't we mention the constant value in the definition? For example, let's say a function 6n+4, we denote it as O(n). But it's not true that the definition holds good for all constant value. This holds good only when c >= 10 and n >= 1. For lesser values of c than 6, the value of n0 increases. So why we do not mention the constant value as a part of the definition?

share|improve this question
4  
How do you propose to represent the constant value, exactly? –  Daniel B Oct 29 '12 at 11:49
1  
Taking your point a step further, any terminating function is O(1) if you bound n. –  Brian Oct 30 '12 at 14:12

7 Answers 7

If you have a performance function of 6n + 4, the relevant question is, "6 what?". As one comment asked: what does your constant represent? In physics terms, what are the units of your constant factor?

The reason why O() notation is so widely used to describe algorithm performance is that there is no portable way to answer that question. Different processors will take a different number of clock cycles and different amounts of time to perform the same elementary computation, or they may lump the relevant elementary computations differently. Different computer languages, or different formal and informal descriptions like pseudocode, will represent algorithms in ways that are difficult to compare directly. Even implementations in the same language can represent the same algorithm in different ways -- trivial formatting details like the number of lines aside, you will generally have a wide variety of arbitrary structural choices to implement any given algorithm.

Look at it another way: we use "algorithm" not to describe a particular implementation, but to describe an entire class of potential implementations of the same general procedure. This abstraction ignores the details of implemention in favor of documenting something of general value, and the constant performance factor is one of these details.

That said, algorithm descriptions are often accompanied by folklore, notes, or even actual benchmarks that describe the performance of actual implementations on actual hardware. This gives you a rough idea what kind of constant factor to expect, but it should also be taken with a grain of salt because the actual performance depends on things like how much work went into optimization of a given implementation. Also, in the long term, the relative performance of comparable algorithms tends to drift as the architecture of the latest and greatest processors changes...

share|improve this answer

(since this is a longer answer, read the bolds for a summary)

Let's take your example and walk through it step-by-step, understanding the purpose behind what we are doing. We start with your function and the goal of finding its Big Oh notation:

f(n) = 6n+4

First, let O(g(n)) be the Big Oh notation we are trying to find for f(n). From the definition of Big Oh, we need to find a simplified g(n) where there exists some constants c and n0 where c*g(n) >= f(n) is true for all n's greater than n0.

First, let's choose g(n) = 6n + 4 (which would yield O(6n+4) in Big Oh). In this case we see that c = 1 and any value of n0 will meet the mathematical requirements from our definition of Big Oh, since g(n) always equals f(n):

c*g(n)      >=  f(n)    
1*(6n + 4)  >=  6n + 4    //True for all n's, so we don't need to pick an n0

At this point we've met the mathematical requirements. If we stopped at O(6n+4), it's clear that this is no more helpful than writing f(n), so it would miss the true purpose of Big Oh notation: to understand the general time-complexity of an algorithm! Thus, let's move on to the next step: simplification.

First, can we simplify out of the 6n so the Big Oh is O(4)? No! (Exercise for the reader if they don't understand why)

Second, can we simplify out the 4 so that the Big Oh is O(6n)? Yes! In that case, g(n) = 6n, so:

c*g(n)    >=  f(n)
c*6n      >=  6n + 4     

At this point, let's choose c = 2 since then the left side will increase faster (by 12) than the right side (by 6) for each increment of n.

2*6n      >=  6n + 4

Now we need to find a positive n0 where the above equation is true for all n's greater than that value. Since we already know that the left side is increasing faster than the right, all we have to do is find one positive solution. Thus, since n0 = 2 makes the above true, we know that g(n)=6n, or O(6n) is a potential Big Oh notation for f(n).

Now, can we simplify out the 6 so that the Big Oh is O(n)? Yes! In that case, g(n) = n, so:

c*g(n)      >=  f(n)    
c*n         >=  6n + 4    

Let's pick c = 7 since the left would increase faster than the right.

7*n         >=  6n + 4

We see that the above will be true for all n's greater than or equal to n0 = 4. Thus, O(n) is a potential Big Oh notation for f(n). Can we simplify g(n) anymore? Nope!

Finally, we've found that the simplest Big Oh notation for f(n) is O(n). Why did we go through all this? Because now we know that f(n) is linear, since it's Big Oh notation is of linear complexity O(n). The nice thing is that now we can compare the time-complexity of f(n) to other algorithms! For example, we now know that f(n) is of comparable time-complexity to the functions h(n) = 123n + 72, i(n) = n, j(n) = .0002n + 1234, etc; because using the same simplification process outlined above they all have linear time-complexity of O(n).

Sweet!!!

share|improve this answer
    
Hi, Good explanation. I still have few doubts. 1. We cannot make the 6n+4 as O(4) since there is a variable value 'n'. Is this the answer? 2. while simplification you chose c=7 and correspondingly calculated n0 to 4. What made to decide c=7 and not less than 7? because based on the value of c the n0 will change. –  Pradeep Nov 15 '12 at 16:57
    
@Pradeep: For 1, you are correct. For a deeper explanation: If we try O(4), that would make our inequality equation c*4 >= 6n+4, and for any c we picked, we could always find a value where all values of n above that would make the inequality false. –  Briguy37 Nov 15 '12 at 22:46
    
@Pradeep: For 2, the actual values of c and n0 are not important. What IS important is that n0 exists for the c we pick. In order for this to be true, the left side of the inequality must increase faster than the right side for large values of n. c=6 is no good for this (6n >= 6n+4 is never true), so I picked c=7. I could have just as easily picked c=10, c=734, or c=6.0000001 and would still have been able to see that there was some n0 that existed to make the inequality true for n >= n0, which means the Big Oh we are testing is valid. –  Briguy37 Nov 15 '12 at 22:47
    
Thanks for clear explanation. This is what i was precisely looking for. Thanks once again. –  Pradeep Nov 16 '12 at 1:35
    
@Pradeep: Glad I could help :) –  Briguy37 Nov 16 '12 at 14:26

The whole notion of Big-Oh notation is specifically to ignore constants and present the most important part of the function describing the run-time of an algorithm.

Forget the formal definition for a moment. Which is the worse (faster growing) function, n^2 - 5000 or 5000 n + 60000? For n less than around 5000, the linear function is greater (and thus worse). Beyond that (exact value 5013?), the quadratic equation is bigger.

Since there are more (quite a few more) positive numbers greater than 5000 than less, we take the quadratic to be the 'bigger' (worse) function in general. Order notation (Big-Oh etc) enforces that (you can always eliminate an additive and a multiplicative constant using those definitions).

Of course, things aren't always simple. Sometimes you do want to know those constants. Which is better Insertion sort or Bubble sort? Both are O(n^2). But one really is better than the other. With more elaborate analysis one can get constants like you are wondering about. It's usually much easier to compute the Big-Oh function than a more exact function.

Big-Oh ignores these constants to simplify and make the most important comparisons easier. We like the notation because usually we don't want to know about the (mostly irrelevant) constants.

share|improve this answer

In algorithm analysis, Order of Growth is the key abstraction and it gives the rate at which the running time changes as the input size changes. Let's say an algorithm has a running time f(n) = 2n + 3. Now we plug in some input size,

n = 10: 2 * 10 + 3 = 23

n = 100: 2 * 100 + 3 = 203

n = 10000: 2 * 10000 + 3 = 20003

n = 1000000: 2 * 1000000 + 3 = 2000003

n = 100000000 : 2 * 100000000 + 3 = 200000003

As can be seen, order of growth is mainly determined by the variable n; constants 2 and 3 are less significant and as the input size grows they become even less significant in determining it. This is why in algorithm analysis constants are subsided in favor of the variable determining the order of growth of a function.

share|improve this answer

There are several reasons, but probably the most important one is that constants are a function of the implementation of the algorithm, not the algorithm itself. The order of an algorithm is useful for comparing algorithms irrespective of their implementation.

The actual runtime of a quicksort will typically change if it's implemented in C or Python or Scala or Postscript. The same applies for bubble sort -- the runtime will vary widely based on implementation.

However, what will not change is the fact that, all else being equal, as the dataset gets larger the time required to run a bubble sort will increase faster than the time required to run quicksort in the typical case, no matter what language or machine they're implemented with, assuming a reasonably correct implementation. This simple fact allows you to make intelligent inferences about the algorithms themselves when concrete details are not availble.

The order of an algorithm filters out factors that, while important in actual real-world measurements, tend to just be noise when comparing algorithms in the abstract.

share|improve this answer

O(n) and other order notation is (typically) not concerned with the behavior of functions for small values. It is concerned with the behavior of functions for very large values, namely limits as n moves toward infinity.

The constants technically matter but they are typically abstracted away as once n becomes large enough, c's value is entirely irrelevant. If c's value is important we can include it in the analysis but unless the functions being compared have very large constant factors or if the efficiency is an especially important concern, they typically are not.

share|improve this answer
    
For example building the pyramids is O(n), sorting pictures of them is O(n log n) - at some point you could have enough pyramids that it would take longer to sort the pictures than build a new one! But only for a very large number of pyramids! –  Martin Beckett Oct 29 '12 at 16:59
    
Good answer, but for a given N, and two algorithms that typically fall into the same "family" of complexities, there can be merit in doing exactly what the OP suggests and including at least the relative coefficients. A linear algorithm with double the number of instructions per element as another could be termed *O*(2N) to the second alg's *O*(N) to show the relative difference, because for any N, the first algorithm will always be double the execution time of the second; however, when comparing to a function of a different complexity family, such as *O*(NlogN), coefficients don't matter. –  KeithS Oct 29 '12 at 17:19

Big O notation as per definition states that:
For a given function g(n), we denote by O(g(n)) the set of functions:
O(g(n)) = {f(n): there exist positive constants c and n' such that 0<=f(n)<=c.g(n) for all n > n'}

The Big O notation is built on the intuition that for all values n at and to the right of n', the value of f(n) is on or below c.g(n).
The constants also don't matter when you go to high valued (variable) factors (like n-square or n-cube) since they are just the constants and not the varying quantities which can become as big as those factors.
Given below is the graph of Big-O notation.
enter image description here

The essence of this notation is in the fact "how lower is f(n) from c.g(n) and not when it starts becoming lower".

share|improve this answer
    
In that case for every O(n) is also Big theta of n since as per definition for some constant it will be a lower bound and for some constant it is a upper bound. for example 6n+4 is also a big theta (n) since when c is less than 10 it is always the lower bound. and when c is more than 10 it is an upper bound. So can we say that for any given Big Oh notation is also a Big theta? –  Pradeep Oct 29 '12 at 4:05
1  
You are saying it the other way around: "Big Theta means Big Oh". And Big -Oh can be replaced with Big-Theta for asymptotically tight bounds. –  Vaibhav Agarwal Oct 29 '12 at 4:10

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.