Big O With Go
Fast recall
Quick revision
Core answer
Whether you understand Big O With Go beyond memorized syntax.
Giving a definition without explaining a practical trade-off.
Connect the concept to a small production example and state its complexity or failure mode.
Interview-ready guide
Interview answer
The ladder, each with the Go example:
// O(1): hash map lookup — constant, regardless of size
m := map[string]int{...}
v := m["key"] // one hash, one check
// O(log n): binary search — halve the search space each step
func binarySearch(arr []int, target int) int {
lo, hi := 0, len(arr)-1
for lo <= hi {
mid := lo + (hi-lo)/2
if arr[mid] == target { return mid }
if arr[mid] < target { lo = mid + 1 } else { hi = mid - 1 }
}
return -1 // 1000 elements: ~10 steps (2^10 > 1000)
}
// O(n): linear scan — touch each element once
for _, v := range arr { if v == target { ... } }
// O(n log n): sorting
sort.Ints(arr) // each of n elements placed via log-n comparison
// O(n²): nested loops — every pair
for i := range arr { for j := range arr { ... } }
// O(2^n): naive fibonacci — each call spawns two
func fibRec(n int) int { if n <= 1 { return n }; return fibRec(n-1) + fibRec(n-2) }The numbers that matter: n=1000 — O(n) is 1000 ops, O(log n) is ~10, O(n²) is 1,000,000. The gap between log n and n² is the difference between instant and never.
The space companion: O(1) in-place sort, O(n) for a copy, O(log n) recursion depth. Interviewers check both.
Big O With Go
Direct Answer
O(1) map lookup, O(log n) binary search, O(n) linear scan, O(n log n) sort, O(n²) nested loops, O(2^n) naive recursion. Interview shorthand for how runtime scales with input size.
Deep Dive & Architecture
The formal definition, simply: f(n) is O(g(n)) if f(n) ≤ c·g(n) for large n — 'the growth rate is at most proportional to g(n).' The practical consequences:
Log n is the halving ladder: each step halves the problem — 1M elements in 20 steps, 1B in 30. This is why binary search on sorted data scales to any size.
The n-log-n floor for comparison sorting: any sort that only COMPARES elements (not radix/counting) has a proven lower bound of Ω(n log n) — the information-theoretic argument (n! orderings, each comparison distinguishes 2, so ≥ log2(n!) ≈ n log n).
The amortized concept: a map insertion is O(1) amortized — occasionally O(n) (the rehash), but averaged over n insertions, each is constant. The worst-single-op and the amortized cost are both honest numbers for different questions.
The interview discipline: name the complexity AND the reason (loop structure, halving pattern, hash function), then state the space cost. 'O(n) because single pass; O(n) space because we build a lookup map.' The reason matters more than the letter.
Common Mistakes & Pitfalls
Giving a definition without explaining a practical trade-off.
Check your understanding
Answer these without looking back at the article.
- When would you use Big O With Go in a real project?
- How would you compare Big O With Go with an alternative?
- What is a common mistake when using Big O With Go?
Looking for a structured roadmap?
Every module on this page is also part of the full Java backend interview track.