Ikki yo'lda maktabga borish mumkin: biri 500 metr, ikkinchisi 5 kilometr. Masofaning aniq metri unchalik muhim emas — muhimi, qaysi yo'l 10 barobar uzoqroq ekanini bilish. Big O yozuvi ham dasturlashda xuddi shunday ishlaydi: algoritm aniq necha millisekund ishlashini emas, balki ma'lumot kattalashganda vaqt qanday o'sishini tasvirlaydi.

Shu kursda ko'rgan ikkita qidiruv usulini solishtiramiz: oddiy "boshidan oxirigacha qidirish" (O(n), "chiziqli") va Binary Search (O(log n), "logarifmik"). O(n) degani: ma'lumot 2 barobar oshsa, vaqt ham taxminan 2 barobar oshadi. O(log n) degani: ma'lumot 2 barobar (hatto 1000 barobar) oshsa ham, vaqt juda oz oshadi — chunki har qadamda yarmi tashlanib boriladi.

package main

import "fmt"

func linearSearchCount(nums []int, target int) int {
	comparisons := 0
	for _, n := range nums {
		comparisons++
		if n == target {
			break
		}
	}
	return comparisons
}

func binarySearchCount(nums []int, target int) int {
	comparisons := 0
	low, high := 0, len(nums)-1
	for low <= high {
		comparisons++
		mid := (low + high) / 2
		if nums[mid] == target {
			break
		}
		if nums[mid] < target {
			low = mid + 1
		} else {
			high = mid - 1
		}
	}
	return comparisons
}

func main() {
	nums := make([]int, 1000)
	for i := range nums {
		nums[i] = i
	}
	fmt.Println(linearSearchCount(nums, 999)) // eng oxirgi element
	fmt.Println(binarySearchCount(nums, 999))
}

1000 ta elementli ro'yxatda, eng oxirgi elementni qidirish uchun chiziqli qidiruvga 1000 marta solishtirish kerak bo'ladi — chunki u bittalab, boshidan yuradi. Binary Search'ga esa bor-yo'g'i 10 marta solishtirish yetadi! Bu tasodif emas: log₂(1000) ≈ 10. Agar ro'yxat 1 million elementli bo'lsa ham, Binary Search'ga faqat ~20 marta solishtirish kerak bo'lardi — chiziqli qidiruvga esa 1 million marta.

Big O'da odatda uchraydigan darajalar (tezdan sekinga): O(1) (doimiy — masalan xarita orqali qidirish), O(log n) (Binary Search), O(n) (chiziqli qidiruv), O(n log n) (yaxshi saralash algoritmlari), O(n²) (Bubble Sort — ikkita ichma-ich sikl). Kod yozayotganda "bu ichma-ich sikl bormi?" degan savol — ko'pincha "bu O(n²) bo'lib qolmayaptimi?" degan savolning boshqacha ko'rinishi.