Big-O notation describes the efficiency of an algorithm in terms of time or space complexity. It helps estimate how an algorithm performs as the input size grows (n → ∞).
| Notation | Name | Growth Rate | Example Algorithm |
|---|---|---|---|
| O(1) | Constant Time | Fastest | Hash table lookup |
| O(log n) | Logarithmic | Very Fast | Binary search |
| O(n) | Linear Time | Moderate | Linear search |
| O(n log n) | Log-Linear | Efficient | QuickSort, MergeSort |
| O(n²) | Quadratic | Slow | Bubble Sort |
| O(2ⁿ) | Exponential | Very Slow | Recursive Fibonacci |
| O(n!) | Factorial | Impractical | Traveling Salesman |
🔹 Logarithms (O(log n)): The number of operations needed halves with each step. Binary search is a great example.
🔹 Quadratic Growth (O(n²)): Each new input increases work exponentially. Sorting algorithms like Bubble Sort perform poorly here.
🔹 Exponential Growth (O(2ⁿ)): Recursion-based algorithms, such as solving the Fibonacci sequence recursively, can become extremely slow for large inputs.
package main
import "fmt"
func linearSearch(arr []int, target int) int {
for i, num := range arr {
if num == target {
return i
}
}
return -1
}
func main() {
nums := []int{10, 20, 30, 40, 50}
fmt.Println("Index of 30:", linearSearch(nums, 30)) // Output: 2
}
🔹 Best for small datasets where sorting is not an option.
🔹 Inefficient for large datasets – requires scanning every element.
package main
import (
"fmt"
"sort"
)
func binarySearch(arr []int, target int) int {
left, right := 0, len(arr)-1
for left <= right {
mid := left + (right-left)/2
if arr[mid] == target {
return mid
} else if arr[mid] < target {
left = mid + 1
} else {
right = mid - 1
}
}
return -1
}
func main() {
nums := []int{10, 20, 30, 40, 50}
fmt.Println("Index of 30:", binarySearch(nums, 30)) // Output: 2
}
🔹 Requires a sorted array but is much faster than linear search.
🔹 Halves the search space at each step, reducing complexity to O(log n).
package main
import "fmt"
func bubbleSort(arr []int) {
n := len(arr)
for i := 0; i < n-1; 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]
}
}
}
}
func main() {
nums := []int{64, 34, 25, 12, 22, 11, 90}
bubbleSort(nums)
fmt.Println("Sorted array:", nums)
}
🔹 Simple, but inefficient – each pass compares every element.
🔹 Only useful for educational purposes, not real-world use.
package main
import "fmt"
func quickSort(arr []int) []int {
if len(arr) < 2 {
return arr
}
pivot := arr[len(arr)/2]
left := []int{}
right := []int{}
middle := []int{}
for _, num := range arr {
if num < pivot {
left = append(left, num)
} else if num > pivot {
right = append(right, num)
} else {
middle = append(middle, num)
}
}
return append(append(quickSort(left), middle...), quickSort(right)...)
}
func main() {
nums := []int{64, 34, 25, 12, 22, 11, 90}
fmt.Println("Sorted:", quickSort(nums))
}
🔹 Divides & conquers – selects a pivot and recursively sorts subarrays.
🔹 Much faster than Bubble Sort for large datasets.
package main
import "fmt"
type Graph map[int][]int
func bfs(graph Graph, start int) {
visited := map[int]bool{start: true}
queue := []int{start}
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
fmt.Print(node, " ")
for _, neighbor := range graph[node] {
if !visited[neighbor] {
visited[neighbor] = true
queue = append(queue, neighbor)
}
}
}
}
func main() {
graph := Graph{
1: {2, 3},
2: {4, 5},
3: {6},
4: {},
5: {},
6: {},
}
bfs(graph, 1) // Output: 1 2 3 4 5 6
}
🔹 Explores all neighbors before going deeper.
🔹 Useful for shortest path problems.
| Use Case | Best Algorithm | Reason |
|---|---|---|
| Searching for an item in an unsorted list | Linear Search (O(n)) | Works without sorting |
| Searching for an item in a sorted list | Binary Search (O(log n)) | Much faster |
| Sorting a small dataset | Bubble Sort (O(n²)) | Simple, but inefficient |
| Sorting a large dataset | QuickSort (O(n log n)) | Faster for large inputs |
| Finding shortest path in a graph | BFS (O(V+E)) | Works well for unweighted graphs |
| Finding shortest path with weights | Dijkstra's Algorithm (O((V+E) log V)) | Best for weighted graphs |
🚀 Now let’s dive into data structures like red-black trees and linked lists!