O(n) vs O(1)

When we say an algorithm is O(n), we imply that it takes n steps to take this algorithm from start to finish, given n is the number of input, or in the array case, the length of an array.

For example, let's look at the following code snippet.

public class App {
    public static void main(String[] args) throws Exception {
        String[] arr = {"h", "e", "l", "l", "o"};
        for (int i = 0; i < arr.length; i++) {
              System.out.println(arr[i]); // runtime: O(n)
        }
    }
}

In the main function of the class App, we do System.out.println() arr.length times, with arr.length equals n. When our array has 10,000 elements, we run through this array 10,000 times, printing 10,000 lines. On the contrary, with an empty array, we exit the function and nothing is printed. O(n) might not be a good option for us if we are dealing with a trillion records of data, which is often the case, especially at the big corps.

Compared to O(n), O(1) seems like heaven. Can you guess what it is?

When we say our algorithm is O(1), we are executing through the code constant time. It doesn't matter how large or small our input is, it only takes one operation for the code to go from the beginning of a statement to its end.

public class App {
      public static void main(String[] args) throws Exception {
            String[] arr = {"h", "e", "l", "l", "o"};
            System.out.print(arr[0]); // runtime: O(1)
      }
}

We know from looking at our code that our arr can get really, really large. However, since we only care about arr[0], which is its first element, it will only take us constant time to finish the function. The same thing will apply if we want to print only the first 5 elements of an array. That'll be O(5). When we get to know more about our Big-O, we'll know that O(5) = O(5 * 1). We'll drop the 5 and consider this piece of code is constant time, O(1).

Next post, we'll discuss the pros and cons of an array.