Big O and Time Complexity

With my technical skills being potentially put to more of a test than ever I’ve done some research on a couple of topics that were kind of new to me. One of the terms I’m seeing a bunch of as I get deeper into my job search is Big O Notation. What I’ll give here are some insights into what I’ve learned on the topic so far. Big O notation is a way for programmers to tell how long a program will take to run. The time the program takes to run can be linear, constant, or quadratic.

Linear or O(n) is what we use to describe the length of the function when it depends on the input given to it to determine its time complexity. If the run time changes based on say, the length of an array, every element in the array will be n in the O(n). I saw it like this as well and it helped me. (n) => F(n). “n” is being passed into a function. For every n that is passed in, it could increase time complexity. If I have a function like the one below:

The time this function takes to run is based on what the value of n is being passed into my function so. If I were to pass in array the run time would be shorter than if I were to pass in array2 based on the number of elements in the array. This makes the time complexity of this program linear. Meaning that as the number of elements increases the amount of time it takes to run will increase with it. In Big O notation this is written as O(n) and called “Big O of n” or “O of n”.

Constant or O(1) is used to describe programs that run with constant time complexity. This means that it doesn’t matter that the value of n is that the program will always take the same amount of time to run. For example:

This function takes an argument(which is completely unneeded) and only does the same thing each time it is called. It simply console logs the sum which is set to zero inside of the function. It doesn’t matter what you give it in terms of an argument it will always just console log zero. The time complexity of this is constant because it will always take the same amount of time to run. Not taking into consideration how fast your computer is, processor speed so on and so forth. This is marked in Big O notation as O(1) and can be pronounced as “Big O of one”.

Quadratic or O(n²) is used to describe run times that are based on functions that are usually nested. Meaning, for example, a loop inside of a loop is used. These functions take the most amount of time because they are based on such large amounts of information. If n is nested data a function will usually have to run once for every index and then run again (while inside of that index) to go through additional indexes. The n for O(n²) means that n is going to be an extremely high(usually) number of elements the computer has to run through to find a solution. One of the times this happens is when the given input is given in the form of nested data such as:

In this example, the program has to do one thing for every element inside of each element inside of the array. This can make run times take a sharp dip upwards as they are running functions inside of functions.

This is an example of a loop inside of a loop that runs generally when dealing with nested data. This means the time complexity usually takes longer and is referred to as quadratic or in Big O, O(n²).

Here you can see an example of different time complexities. Notice how the O(n²) uses a particularly large amount of time and the line itself has a steep rise in the amount of time it takes. You also see O(n) and O(1). O of n being a straight line or linear and O of 1 being constant, the time never changes.

This is a brief overview of Big O notation and time complexity.

Related posts:

When Abram prostrated himself, God spoke to him: “My covenant with you is this: you are to become the father of a host of nations. No longer shall you be called Abram; your name shall be Abraham, for…

As people celebrate the victories and success that has been achieved in the past 12 months, lots of them start setting goals and making plans for the next spin around the Sun. Looking back at what…