O(…) and how to calculate it

algorithmsbig ocomplexity

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.

Best Answer

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:

Related Topic