Data Strctures And Algorithm

• Big O Notation is used to describe the performance of an alogrithm.
• It is used to check if the algorithm is going scale well if the input grows really large.
• O(n)

O(1)

• O(1) notation
• It doesn't matter how big the array is. It can be either one or one million items.
• All we are doing below is printing the first item.
• Below method has a single operation and takes constant amount of time to run.
• The runtime complexity of the below method is: O(1).

package main

func bigO1(input []int) {
    fmt.Println(input[0])
}

• Note: When talking about the runtime complexity, we don't really care about the number of operations, we just want to know how much an algorithm slows down as the input grows larger.

O(n)

• O(n) notation
• If we have one item in the array we are going to have one print operation, if we are gonna have million items on an array, we are going to have million print operation.

package main

func bigOn(input []int) {
    // O(1 + n + 1) => O(2 + n) => O(n)
    fmt.Println() // O(1)
    for _, v := range input { // O(n)
        fmt.Println(v)
    }
    fmt.Println() // O(1)
}

• The cost of the algorithm grows linearly and in direct correlation with the size of the input.
• The runtime complexity of the above method is: O(n). Where n represents the size of the input, as n grows cost of the algorithm also grows linearly.
• O(1 + n + 1) => O(2 + n) => O(n) While using Big O notation we drop these constants, we don't really matter, if our array has 1 million inputs adding 2 extra print operation will have a significant impact on our cost of the algorithm, the cost of our algorithm still increases linearly.

O(n^2)

• O(n^2) notation
• We can say this algorithm run in a quadratic time instead of linearly.

package main

// printing all combinations of the items in an array
func bigOn2(items []int) {
    // O(n^2)
    for _, x := range items {
        for _, y := range items {
            fmt.Println(x, y)
        }
    }
}

• Note: Algorithms that runs in O(n^2) is slower than O(n)