Big O Notation

Understanding algorithmic complexity and performance analysis.

Common Time Complexities

1. O(1) - Constant Time

// O(1) example - array access
func Get_First(arr []int) int {
    if len(arr) == 0 {
        return -1
    }
    return arr[0]
}

2. O(log n) - Logarithmic Time

// O(log n) example - binary search
func Binary_Search(arr []int, target int) int {
    left, right := 0, len(arr)-1
    for left <= right {
        mid := (left + right) / 2
        if arr[mid] == target {
            return mid
        }
        if arr[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return -1
}

3. O(n) - Linear Time

// O(n) example - linear search
func Linear_Search(arr []int, target int) int {
    for i, v := range arr {
        if v == target {
            return i
        }
    }
    return -1
}

4. O(n log n) - Linearithmic Time

// O(n log n) example - merge sort
func Merge_Sort(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }

    mid := len(arr) / 2
    left := Merge_Sort(arr[:mid])
    right := Merge_Sort(arr[mid:])
    
    return merge(left, right)
}

func merge(left, right []int) []int {
    result := make([]int, 0, len(left)+len(right))
    i, j := 0, 0

    for i < len(left) && j < len(right) {
        if left[i] <= right[j] {
            result = append(result, left[i])
            i++
        } else {
            result = append(result, right[j])
            j++
        }
    }

    result = append(result, left[i:]...)
    result = append(result, right[j:]...)
    return result
}

5. O(n²) - Quadratic Time

// O(n²) example - bubble sort
func Bubble_Sort(arr []int) {
    n := len(arr)
    for i := 0; i < n; i++ {
        for j := 0; j < n-i-1; j++ {
            if arr[j] > arr[j+1] {
                arr[j], arr[j+1] = arr[j+1], arr[j]
            }
        }
    }
}

Space Complexity Examples

1. O(1) Space

// O(1) space - in-place operation
func Reverse_Array(arr []int) {
    for i, j := 0, len(arr)-1; i < j; i, j = i+1, j-1 {
        arr[i], arr[j] = arr[j], arr[i]
    }
}

2. O(n) Space

// O(n) space - creating new array
func Copy_Array(arr []int) []int {
    result := make([]int, len(arr))
    copy(result, arr)
    return result
}

Resources

Books

1. "Introduction to Algorithms" by CLRS

2. "Grokking Algorithms" by Aditya Bhargava

3. "Data Structures and Algorithms in Go" by Hemant Jain

Online Resources

1. Big O Cheat Sheet

2. GeeksforGeeks - Time Complexity

3. Go Documentation - Performance

Video Tutorials

1. MIT 6.006 Introduction to Algorithms

2. Coursera - Algorithms Specialization

Practice Platforms

1. LeetCode

2. HackerRank

3. CodeWars