Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Help! I have a question where I need to analyze the Big-O of an algorithm or some code.

  • I am unsure exactly what Big-O is or how it relates to Big-Theta or other means of analyzing an algorithm's complexity.

  • I am unsure whether Big-O refers to the time to run the code, or the amount of memory it takes (space/time tradeoffs).

  • I have Computer Science homework where I need to take some loops, perhaps a recursive algorithm, and come up with the Big-O for it.

  • I am working on a program where I have a choice between two data structures or algorithms with a known Big-O, and am unsure which one to choose.

How do I understand how to calculate and apply Big-O to my program, homework, or general knowledge of Computer Science?

Note: this question is a canonical dupe target for other Big-O questions as determined by the community. It is intentionally broad to be able to contain a large amount of useful information for many Big-O questions. Please do not use the fact that it is this broad as an indication that similar questions are acceptable.

share|improve this question
Just a note, this question is being discussed on meta here. – enderland Oct 28 '15 at 20:14
up vote 11 down vote accepted

The O(...) refers to Big-O notation, which is a simple way of describing how many operations an algorithm takes to do something. This is known as time complexity.

In Big-O notation, the cost of an algorithm is represented by its most costly operation at large numbers. If an algorithm took n3 + n2 + n steps, it would be represented O(n3). An algorithm that counted each item in a list would operate in O(n) time, called linear time.

For a list of the names and classic examples on Wikipedia: Orders of common functions

Related material:

share|improve this answer

protected by Thomas Owens Oct 28 '15 at 19:49

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.