Ebi's Dev Life

Data Structure and Algorithm (Big O notation)

Data Structure and Algorithm (Big O notation)

Titilayo Soremekun's photo
Titilayo Soremekun
·

4 min read

When going into DSA, the first thing we need to understand is the basic terms, so let's get into it.

What is an algorithm?

We can simply explain an algorithm as a set of instructions for accomplishing a task.

What is a data structure?

The data structure is a way of organizing data so that it can be used effectively.

Now, this brings us to Big O notation, which is used to analyze the algorithm we create to figure out the time and space complexity.

A DSA problem can be solved in many ways, but it is important to always go with the 'Better' approach. When we say better, what do we mean?

  • Faster
  • Less memory-intensive

  • More readable

    The running time of an algorithm depends on how long it takes a computer to run the lines of code of the algorithm. That depends on the speed of the computer, the programming language, and the compiler that translates the program from a language into code that runs directly on the computer. We can calculate the time and space complexity of our code using the Big O notation. This is done by counting the number of operations the computer has to perform.

We can use a combination of two ideas. First, we need to determine how long the algorithm takes, in terms of the size of its input. The second idea is that we must focus on how fast a function grows with the input size. We call this the rate of growth of the running time.

Let's take this example; Suppose we want to write a function that calculates the sum of all numbers from 1 up to (and including ) some number n example n = 6 output = 1 + 2 3 4 5 6 = 21 

function addUpTo(n) {
return n * (n + 1) / 2; 
}
// Time complexity of O(1) 
//Space complexity of O(1)

In this operation, we have 1 multiplication, 1 addition, and 1 division. That is, we have only three operations regardless of the size of n.

let's look at this second code, that solves the same problem.

function addUpTo(n)  {
let total = 0;       // declare an total variable that 
for (let i = 1; i <= n; i++){    // we loop through n, starting at 1 to n and adds them to total variable.  
total += i; // we return total 
}
return total;
}

// Time complexity of O(n) because we looped linearly through n 
//space complexity of O(1) because we maintained the same space

Here,

  • We have an operation, the n assignment ' = ', and the n additions ' + '.
  • The loop, goes through all of the numbers one by one(linearly). If n is 6, it loops through 6 times, if n is 1 billion, it loops through 1 billion times
  • We have single assignments and comparisons (i = 1; i < n )

Time complexity

When determining the time complexity of an algorithm, there are some rules, we can use;

Constants don't matter.

  1. O(700) can be simplified to O(1) as this just means we have 700 operations, no matter how much n is. It means it has a constant runtime. It takes the same time to calculate 2 + 2 and 100,00,000 + 10.

  2. O(2n) can be simplified to O(n) as variable assignments are also constant. It takes the same time to make a variable x = 1,000 compared to x = 100,000,000. It's roughly the same.

  3. Accessing elements in an array(by index) or object (key) is constant. In a loop, the complexity is the length of the loop times the complexity of whatever happens inside the loop O(6n2) can be simplified to O(n2) 6, n, squared n squared

Space complexity

This analyzes how much additional memory we need to allocate to run the code in our algorithm. We can also say it's the amount of memory that's taken up in our code.

Things to note;

  • Most primitives (Booleans, numbers, undefined, null) are constant space.
  • Strings require O(n) space (where n is the string length) Example, if the string grows to 50 characters, it requires 50 more space.
  • Reference types are generally O(n), where n is the length (for arrays) or the number of keys (for objects).

Takeaways

  • To analyze the performance of an algorithm, we use Big O notation.
  • Big O notation can give us a high-level understanding of the time or space complexity of an algorithm.
  • Big O notation doesn't are about precision, only about general trends (linear ? constant ? quadratic ?)
  • The time or space complexity (as measured by Big O) depends only on the algorithm, not the hardware used to run the algorithm.

Suggested Resources for further readings

These are some of the resources I currently use in learning DSA are;

data structuresalgorithms