Explore BrainMass

C++ big O notation

What does "n" represent in relation to big O notation? In other words, what does it mean? Like in O(n). I need a definition of what n is in words.

Solution Preview

Big O notation is used throughout computer science to show how algorithms behave as their inputs grow larger. It is not specific to C++; it is useful in all programming languages and in theoretical computer science.

The idea is to summarize how many steps an algorithm takes to run. But instead of just saying a number like 1,000, big O notation gives the answer as a function, for example O(n^2). Here, "n" is the size of the input to the algorithm and the algorithm takes approximately n^2 steps to run. This is much more useful than just having a single data point, such as "when the input has size 30, the algorithm takes 900 steps to run." We'd much rather have a function giving the number steps of running time for every possible input size.

For example, take ...

Solution Summary

The solution discusses and defines what the "n" represents in relation to the big O notation.