BigO

[japananh]

BigO

Time complexity

Space complexity

• Space complexity is a measure of the amount of memory or auxiliary space required by an algorithm as a function of the input size. It helps to analyze how efficiently an algorithm uses memory.
• Use cases: Space complexity is particularly relevant when you need to optimize memory usage, which is important in many real-world scenarios.
• Time complexity: O(n log n)
• Space complexity: O(log n)
• Demo:

package main

import "fmt"

func quickSort(arr []int) {
	if len(arr) <= 1 {
		return
	}

	pivot := arr[0]
	less := make([]int, 0)
	greater := make([]int, 0)

	for _, num := range arr[1:] {
		if num <= pivot {
			less = append(less, num)
		} else {
			greater = append(greater, num)
		}
	}

	quickSort(less)
	quickSort(greater)

	copy(arr, less)
	arr[len(less)] = pivot
	copy(arr[len(less)+1:], greater)
}

func main() {
	arr := []int{3, 6, 8, 10, 1, 2, 1}
	quickSort(arr)
	fmt.Println(arr)
}