What is the use of Big-O notation in computer science if it doesn't give all the information needed?

For example, if one algorithm runs at `1000n`

and one at `n`

, it is true that they are both `O(n)`

. But I still may make a foolish choice based on this information, since one algorithm takes 1000 times as long as the other for any given input.

I *still* need to know *all* the parts of the equation, including the constant, to make an informed choice, so what is the importance of this "intermediate" comparison? I end up loosing important information when it gets reduced to this form, and what do I gain?

It's main purpose is for rough comparisons of logic. The difference of `O(n)`

and `O(1000n)`

is large for `n ~ 1000`

(n roughly equal to 1000) and `n < 1000`

, but when you compare it to values where `n >> 1000`

(n much larger than 1000) the difference is miniscule.

You are right in saying they both scale linearly and knowing the coefficient helps in a detailed analysis but generally in computing the difference between linear (`O(cn)`

) and exponential (`O(cn^x)`

) performance is more important to note than the difference between two linear times. There is a larger value in the comparisons of runtime of higher orders such as and Where the performance difference scales exponentially.

The overall purpose of Big O notation is to give a sense of relative performance time in order to compare and further optimize algorithms.

You're right that it doesn't give you *all* information, but there's no single metric in any field that does that.

Big-O notation tells you how *quickly* the performance gets worse, as your dataset gets larger. In other words, it describes the type of performance *curve*, but not the absolute performance.

As you correctly noted, it does not give you information on the exact running time of an algorithm. It is mainly used to indicate the *complexity* of an algorithm, to indicate if it is linear in the input size, quadratic, exponential, etc. This is important when choosing between algorithms if you know that your input size is large, since even a `1000n`

algorithm well beat a `1.23 exp(n)`

algorithm for large enough `n`

.

In real world algorithms, the hidden 'scaling factor' is of course important. It is therefore not uncommon to use an algorithm with a 'worse' complexity if it has a lower scaling factor. Many practical implementations of sorting algorithms are for example 'hybrid' and will resort to some 'bad' algorithm like insertion sort (which is `O(n^2)`

but very simple to implement) for `n < 10`

, while changing to quicksort (which is `O(n log(n))`

but more complex) for `n >= 10`

.

Big-O tells you how the runtime or memory consumption of a process changes as the size of its input changes. O(n) and O(1000n) are both still O(n) -- if you double the size of the input, then for all practical purposes the runtime doubles too.

Now, we can have an O(n) algorithm and an O(n^{2}) algorithm where the coefficient of n is 1000000 and the coefficient of n^{2} is 1, in which case the O(n^{2}) algorithm would outperform the O(n) for smaller n values. This doesn't change the fact, however, that the second algorithm's runtime grows more rapidly than the first's, and this is the information that big-O tells us. There will be some input size at which the O(n) algorithm begins to outperform the O(n^{2}) algorithm.

Generally, Big-O notation is useful to express an algorithm's scaling performance as it falls into one of three basic categories:

- Linear
- Logarithmic (or "linearithmic")
- Exponential

It is possible to do deep analysis of an algorithm for very accurate performance measurements, but it is time consuming and not really necessary to get a broad indication of performance.

In addition to the hidden impact of the constant term, complexity notation also only considers the worst case instance of a problem.

Case in point, the simplex method (linear programming) has exponential complexity for all known implementations. However, the simplex method works much faster in practice than the provably polynomial-time interior point methods.

Complexity notation has much value for theoretical problem classification. If you want some more information on practical consequences check out "Smoothed Analysis" by Spielman: http://www.cs.yale.edu/homes/spielman

This is what you are looking for.

What does that constant factor represent? You can't say with certainty, for example, that an algorithm that is O(1000n) will be slower than an algorithm that's O(5n). It might be that the 1000n algorithm loads all data into memory and makes 1,000 passes over that data, and the 5n algorithm makes five passes over a file that's stored on a slow I/O device. The 1000n algorithm will run faster even though its "constant" is much larger.

In addition, some computers perform some operations more quickly than other computers do. It's quite common, given two O(n) algorithms (call them A and B), for A to execute faster on one computer and B to execute faster on the other computer. Or two different implementations of the same algorithm can have widely varying runtimes on the same computer.

Asymptotic analysis, as others have said, gives you an indication of how an algorithm's running time varies with the size of the input. It's useful for giving you a good starting place in algorithm selection. Quick reference will tell you that a particular algorithm is O(n) or O(n log n) or whatever, but it's very easy to find more detailed information on most common algorithms. Still, that more detailed analysis will only give you a constant number without saying how that number relates to real running time.

In the end, the only way you can determine which algorithm is right for you is to study it yourself and then test it against your expected data.

In short, I think you're expecting too much from asymptotic analysis. It's a useful "first line" filter. But when you get beyond that you have to look for more information.

Similar Questions

I am writing a small program to retrieve list of services and processes running on a remote computer, all is running well. I am using Process for ret list of processes and ServiceController for list o

What's the difference between using oracle's plus notation (+) over the ansi standard join notation? Is there a difference in performance? Is the plus notation deprecated?

Sometimes I get myself using different types of trees in Haskell and I don't know what they are called or where to get more information on algorithms using them or class instances for them, or even so

I am trying to understand of the SpringContextLoaderListener. i.e why we need it? I loosely understand that it is required to start up Spring. http://www.coderanch.com/t/490458/Spring/purpose-ContextL

I'd like some help with an left join statement thats not doing what i, probably incorrectly, think it should do. there are two tables: cd: CREATE TABLE `cd` ( `itemID` int(11) NOT NULL AUTO_INCREMENT,

What concepts in Computer Science do you think have made you a better programmer? My degree was in Mechanical Engineering so having ended up as a programmer, I'm a bit lacking in the basics. There are

I use the word Notation because fabien potencier has its own generator but i can't find what notation (or syntax if you will) it uses for the comments. http://fabien.potencier.org/article/63/sami-yet-

I will be teaching my first university level Computer Science course this summer, and I'm currently working on coming up with ideas for fun assignments that the students will complete. The course is t

What is the purpose of database schema? Where can I find more information about this? It's not table, it's not database, what is it?

The problem is that I have X items of varying weighted values that must go into Y containers. The containers are of differing sizes (e.g. hold differing maximum weights). The total load of each contai

Okay so im trying to make a program where if it's installed on another computer, i can access files on that computer. Is this possible using java? and if so could anyone possibly point me in the right

What could be the purpose of the tilde in this code block? public override int GetHashCode() { return ~this.DimensionId.Id ^ this.ElementId.Id; } ^ Operator (C# Reference) Visual Studio 2010 Binary ^

I know that arrays in C are just pointers to sequentially stored data. But what differences imply the difference in notation [] and *. I mean in ALL possible usage context. For example: char c[] = te

I see this [below] all over in the Android code (and some other code sources). What is its point or purpose? class Foo { int mBar = 1337; static void main(String... args) { System.out.println(isFubar(

This question already has an answer here: Plain English explanation of Big O 21 answers What is Big O notation? Do you use it? I missed this university class I guess :D Does anyone use it and g

Just looking for some clarification, as I am still new to all of this: I have created a rudimentary CMS. We now have to redesign it to allow for an image upload. When I use my original form which I wa

In proving and disproving Big O questions that explicitly say use the definition to prove and disprove, my question is, is what I am doing correct? For example you have a question that is g(n) = O(f(n

I'm a fairly novice programmer - I know some C++ and PHP - and I'm wondering: what would be a good way to learn the conceptual and technological fundamentals of the field (without having to sit throug

I'm trying to write a little matrix program. Using doublke pointers doesnt work so I figure the easiest way is to have a struct that has the #rows and #columns and a 1d array as the matrix. But there

I am currently studying a computer vision module in college. I would like to get a theoretical understanding of what contours are in computer vision and what they are used for.

instead of sqlite openhelper we can able to create,delete,update database in android then what is the purpose of sqlite openhelper can any body explain please.

There are convincing arguments against using namespace std, so why was it introduced into the language at all? Doesn't using namespace defeat the purpose of namespaces? Why would I ever want to write

What is the purpose of $(elem) and when do I use it? I have a problem with my javascript function, I have 3 forms and this 3 forms sometimes share the same field classes, thus when I try to do a verif

What's the purpose of registering a window class via WNDCLASSEX and RegisterClassEx() when creating a window in a Windows API application?

What are some good programs or web-based applications that can be used (preferrably (but not necessarily) for free) to create diagrams for computer science articles or dissertations? Particularly, I'm

I listen to several podcasts about technology like Java, PHP, Linux and then I listen to Software Engineering Radio to help me along with Software Architecture, but I need a good podcast on computer s

I came to a career in software development with a degree in English, rather than Computer Science or another science/engineering background. I have gone a long way on my self-taught basis, but after 1

I have implemented IValidatableObject several times and have never found out what the purpose of parsing ValidationContext to the Validate method is - my typical IValidatableObject implementation look

I understand that exit(1) indicated an error , for example : if (something went wrong) exit(EXIT_FAILURE); But what's the purpose of using exit(EXIT_SUCCESS); ? When handling with processes maybe ?

I have heard these two terms thrown around by people with the same friends. As much as I've heard, computer science is the more mathematically rigorous and its graduates tend to write more code. What

What is a core dump file in linux? What all information does it provide?

Can somebody help me understand the get & set? Why are they needed? I can just make public variable.

Hi i was wondering what is the purpose of using @ModelAttribute why use @RequestMapping(value=) public String index(@ModelAttribute(before) Before b) { System.out.println(b.getBeforeString()); ret

I am Industrial Engineer in Dominican Republic (the Caribbean), i always wanted to Study Computer science when in high school, but i never found in my country a curriculum that seemed as good to decid

private int[] myStuff; /** Precondition: myStuff contains int values in no particular order. /*/ public int mystery(int num) { for (int k = myStuff.length-1; k>=0; k--) { if (myStuff[k] < num) {

What is the purpose of Compile Sources in Xcode? Does every file in your project need to in there? If I add files to a project, does every file get added to compile sources.

Short and sweet: What other zzzzOverflow are? I know: StackOverflow and MathOverflow (and others but with really small and not really valuable people like the mentioned). I'm particulary intrested in

For a project we're working on right now, we want to pull a Donald Knuth and have a version number that converged towards some irrational number. However, we don't want to use something boring like pi

Fibonacci numbers have become a popular introduction to recursion for Computer Science students and there's a strong argument that they persist within nature. For these reasons, many of us are familia

This question already has an answer here: What is the purpose of wrapping whole Javascript files in anonymous functions like “(function(){ … })()”? 5 answers I'm working with the following: de

What is the purpose of Verifiable()? If I verify a Mock and leave this out it still verifies the SetUp. Edit: I was using VerifyAll() thus the reason for everything being verified. After changing to V

So i am trying to make a downloader based on http protocol. It works ok on small txt files, but if i try downloading something bigger, lets say a picture, it doesnt get all of the data. void accel::ge

I have seen some dojo apps at work that utilize layoutContainers but I have not found much in the way of justification for using said cotainers. What is the purpose of a dijit LayoutContainer? Does it

Doing an assignment for my computer science class and can't quite figure out what I'm doing wrong. I have to write a program that adds all the squares between 1 and 100 (1, 4, 9, 16, 25, 36, 49, 64, 8

The following line is apparently written best in dot notation. I am trying to clean my JavaScript code to make it strict. What does it mean? if (ie||ns6) { var tipobj=document.all? document.all[dhtm

In LiveCycle Workbench ES/ES2 there is a 'Synchronize' button as well as a 'Check Out' button that is available for all asset files and folders in the Applications View. What is the purpose of the 'Sy

I'm writing Playframework 2.0 application using Scala and Anorm to access db. Currently I'm using Pk[Long] for id fields and I'm worry about additional get call needed to access actual value. So I st

What is the purpose of this software? http://www.httpwatch.com/

What are practical applications of Queues in Computer Science. Where do we use them and why? I heard that we use them in Video Games and Computer Simulation programs, is that true? Why? Apart from the

What is the fastest way for a Adobe AIR program program to index all images on a users' computer? Using Open Source ActionScript-3, MXML Libs and classes. Fastest - Same pc configuration, different t