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

What is the purpose of using ## in jquery if($('##hidetxt').val().length ==0 ){ $(##hidetxt).val(firstname Asc); } What is the difference of using single # and double ## in jquery

I was spurred to ask the question by an answer I saw for a question on Software Engineering Videos. Here's the answer: As an aside, be careful what you're linking here. Software Engineering and Compu

What could be the meaning of this notation. #pragma warning( disable : 4530 )

I am working on a program that i want to gather system information in order to determine if the computer is compatible with software. I would like to add the program to a website for visitors to check

There's not much info in the spec on what type ascription is, and there certainly isn't anything in there about the purpose for it. Other than making passing varargs work, what would I use type ascr

I am interested in using the AutomationFactory namespace but I cannot find any documentation on what I can use for a sepcific COM. I figure it's because I do not know what terms I should actually be l

Just want to know what is the purpose of active executable in xcode project? Thanks Saurabh

Can someone give me an example of an example of a class hierarchy relevant to computer science? In my lectures I've seen some simple examples like: Vehicle Construction Heavy Machinery Crane Grader

I've looked into some questions here where the best programming books are listed and then thought why there isn't a question concerning speeches yet. I think that speeches or presentations from deve

let's say I have a 2-Mbyte chip and need to construct a 8-Mbyte memory. I need to show the address lines in a diagram and explain what the address lines are used for. How would I go about doing this?

I'm trying to write a python script that retrieves information about publications from ISI Web of Science. I found domoritz's python script wos.py on GitHub. It uses Suds to connect to the ISI Web of

In Java, flush() method is used in streams. But I don't understand what are all the purpose of using this method? fin.flush(); tell me some suggestions.

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

How hard is it for a computer science MS student (with a little knowledge in biology) to research problems related to bioinformatics? How much is bioinformatics related to graph algorithms and data st

I've a string which looks like this: [{text:key 1,value:value 1},{text:key 2,value:value 2},{text:key 3,value:value 3}] I'm not sure what kind of notation this is, AFAIK this is generated

What is the purpose of NLSTERRITORY session variable in Oracle? If I change NLSTERRITORY point to a different country what does it do? Does it change any date parameter? Because always 10Nov2010 is We

Which are the best? Specifically those that would allow one to become a part of a greater community.

Specifically I've seen it used in the context of text filtering. As if predicate == filter criteria. Is this accurate?

What is the complexity of inserting into sorted link list in big-O notation? Let say I have 5 elements and what is the complexity to insert all of them. Thank you very much

What is the possible purpose of this code: if(1 == 1){...}? All I know untill now is what it's called Fictive if.

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

The idea here is to get better programmers right out of college. I think I would have to go with Algorithms, it's not exactly something you can pick up on your own very easily and I think it enables y

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.

Given that interfaces are also used to help hide information, giving the user only a subset of the possible methods they are allowed to use, and, let's say, I have a Person class and interface IPerson

Possible Duplicate: Plain English explanation of Big O I know Big O notation is used to assess how efficient an algorithm is, but I do not understand how you read Big O notation or what exactly how

The title says it all: what CLR version is / will be needed to run C# 6 programs? The CLR version is interesting to find out the system requirements and supported operating systems. I googled [1] [2]

I am a newbie learning the iOS. Can someone please explain what is the purpose of the xcscheme file?

Ok, I know that online there are millions of answers to what OpenGL is, but I'm trying to figure out what it is in terms of a file on my computer. I've researched and found that OpenGL acts as a multi

I'm trying to decide what information my Event DTOs should contain in a pub/sub scenario. I see two possibilities: 1) All the information that could be needed by subscribers interface UserInvitedToGro

I am in an XML class and have the following line of code.. <xsl:value-of select=count(//@qty) /> What is the purpose of the // before the qty attribute? What does it designate?

I want to browse all folders on my computer without using opendir(), in PHP.

What is the purpose of the AuthName directive used within the <Directory></Directory> tag of the httpd.conf file?

What is the BigO complexity of following lgorithms: boolean intersection(TreeSet<?> set1, TreeSet<?> set1){ if(set1.size() > set2.size()){ return intersection(set2, set1); } for (Object

How would i go about gathering information about a system in python? Seems most of the commands are made for Unix... Are there any options in windows? Thanks, Jake.

Wolfram Mathematica 7 has an increasing popularity among computer science and computer engineering students, but what are the main benefits and features it offers?

This isn't a platform specific question - rather I'm interested in the general platform independent areas of computer science that are particularly relevant to mobile applications development. For exa

What is the meaning of this .notation (AlertDialog.Builder) in a class constructor? public Dialog onCreateDialog(Bundle savedInstanceState) { return new AlertDialog.Builder(getActivity()) .setTitle(R

This question already has an answer here: What does it mean to “program to an interface”? 21 answers I have surprisingly never understood the purpose of doing this: Map telephoneNumbers = new H

I am using achartengine with cubic line chart, but it doesnt seem to work. The cubic line chart doesnt pass through all the points in the series. In this example, the graph is far away from the points

What is the purpose of a JMS session? Why isn't a connection alone sufficient to exchange JMS messages between senders and receivers?

I am starting to work with AndEngine and I see that some tutorials use setTouchAreaBindingOnActionDownEnabled but don't explain its purpose. Why I need to use this method together with onAreaTouched?

I found it in a statement like this: delete /*+ restrict_all_ref_cons */ from table_1 where ... Can anyone give some piece of information for what the hint is doing? The database is an Oracle databas

I Googled for a long time but I still don't understand how it works as most of the explanation are very technical and there are no illustrations to make it clearer. My primary confusion is that what i

I am building an app that makes use of google places api,i use this url the desired link doesnt produce any results when i use it in the browser and i use json to parse the data coming from google pla

Hey. I'm taking a course titled Principles of Programming Languages, and I need to decide on a project to do this summer. Here is a short version of what the project needs to accomplish: The nature o

Possible Duplicate: When is JavaScript’s eval() not evil? I know, generally using eval() is bad practice. But for what purpose it is existed there? What is the correct purpose of eval()? At what si

What is the performance in Big-O notation of the following algorithm? It's a function I wrote to print all permutations of a string. I know for an input of length n there are n! different permutations

What permissions are needed for using SQLDependency? I checked books online but it wasn't clear on this point.

I have an array with some values: [1, 2, 3, 4] I'd like to make a new array that contains mapped version of the items in the array above, but only add them to the new array if they pass a truth test.

I'm learning Computer Science course and when I read to these definition, I understand. But I don't know what different purpose of two presentations and why. Here some short explanation of purpose tha