Introduction to Data Structures-Big O

We need different data structures to solve problems. For example, Binary Tree, LinkedList, Array, Stack, etc. Alternatively, on the same data structure, like an Array, we can use different algorithms for sorting, such as Bubble Sort, Insertion Sort, etc. All these choices have consequences for the quality, speed, usability, and resources consumed by our code. Therefore, it’s crucial to know what we’re writing.

Array

Omega represents the best case, Theta the average case, and Omicron (Big O) the worst case. Big O always measuring worst case.

Suppose we have two pieces of code, and both achieve the same thing. How do we decide which one is better? Big O is a way to mathematically understand this, helping us determine which code is more efficient.

Big O understands this in two ways:

1. Time Complexity : Scaling with number of operations
2. Space Complexity : Amount of memory that something uses

Let me show you with an example right away.

function logElements(n) {
    for(let i = 0; i < n; i++) {
        console.log(i)
    }
}

logElements(4)

We passed the function, the number n and this ran n times. In example, we passed 10, and it ran 10 times. Because of this, result is O(n)

O(n) is always going to be a straight line

There are some ways to simplify Big O, and one of those ways is Drop Constants. Let’s try it with an example which includes for loop.

function logElements(n) {
     for(let i = 0; i < n; i++) {
        console.log(i) 
     }
 
     for(let j = 0; j < n; j++) {
        console.log(j) 
     }       
 }
 
 logElements(4)

Output: 0, 1, 2, 3 for first loop and 0, 1, 2, 3 for second loop.

2n, 5n, 400n. The initial constants don’t matter. If there’s a constant, we drop it, and the result becomes O(n)

Let’s try to solve example which includes for loop inside of for loop.

function logElements(n) {
     for(let i = 0; i < n; i++) {
         for(let j = 0; j < n; j++) {
             console.log(i, j) 
         }       
     } 
 }
 
 logElements(4)

The output starts with 0 0, 1 1, … and stops when it reaches 3 3

Solution for Big O is n*n, so it’s n2. Result is O(n2)

O(n) is better than O(n2)

Drop Non-Dominants is another way to simplify Big O

function logElements(n) {
     for(let i = 0; i < n; i++) {
         for(let j = 0; j < n; j++) {
             console.log(i, j) 
         }       
     } 
 
     for(let k = 0; k < n; k++) {
         console.log(k)
     }
 }
 
 logElements(4)

n2 would be any number here. For instance, it would be 100000, so n cannot significantly affect the result.

Let’s do some examples with different results.

function manyItems(n) {
  return n+n+n+n
}

Whether it’s n+n+n+…+n or just n+n, the result doesn’t change. The Big O is O(1). O(1) represents constant time.

O(nlog n) is the efficient as you can make a sorting algorithm

For now, we’ve just touched on the basics; I’ll go into detail in my subsequent articles. I didn’t mention everything in this article, because some topics are complex. Lastly, I’ve included a Big O efficiency graph here. See you in the upcoming articles.