Algorithms in O(n^2) vs O(n) [duplicate]

What you are asking about is a topic in computer science known as Algorithm Complexity Analysis. It is a very important topic to consider when writing algorithms, or solutions, in your programs because it relates to run-time, or how fast your computations will run.

Big-Oh, or O(n) relates to the upper-bound run-time for an algorithm to run. In this case, O(n) means for n-elements there will need to be all n-elements considered for the algorithms computation to complete, or linear. The range for this Big-Oh complexity is from constant time, O(1), to up O(n^n) for really large, and very slow computations. Also, consider equations such as the following:


These both are O(n) complexity because as the number of elements grow, the equation grows larger and larger because of it. We neglect the constants because the equation will grow larger and fast due to the variable, rather than due to the constant values which never change. Whereas, with equation as the following:


The complexity is going to be O(n^2) due to the 10n^2 being the largest growing element contributing to the equation growing faster. We drop the constants and consider the largest growing components to equations to evaluate complexity.

For Big-Omega complexity, we consider this the lower bound for Algorithm Complexity Analysis. For example, an algorithm can run as quick as Omega(n) (best case) but take as long as O(n^2) (worst case) this is common in analysis of sorting algorithms or searching algorithms.

In some cases, we want to write programs with algorithms that are efficient and faster for optimization reasons, especially when we want a quicker program for faster solutions or quicker run times.

The code example you provided is O(n) because it uses a for loop to iterate over n-elements. Consider a double for loop, where there is a second loop within your current for loop. This is O(n^2) due to iterating over, in the worst case, n*n elements.

Java pseudo-code for a O(n^2) run-time initializing an empty matrix:

int result[n][m];
for(int i=0; i<n; ++i){
    for(int j=0; j<m; ++j){
       result[i][j] = 0;

Leave a Comment