Understanding runtime complexity is key to writing efficient code. In this guide, we’ll explore common Big-O complexities using Kotlin code snippets — from the breezy speed of O(1) to the mountainous effort of O(2ⁿ).
O(1) — Constant Time
This is as good as it gets — the operation takes the same time regardless of input size.fun getFirstItem(items: List<Int>): Int? { return items.firstOrNull() }
O(log n) — Logarithmic Time
Typical in binary search or operations that divide the problem in half each time.fun binarySearch(sortedList: List<Int>, target: Int): Boolean { var left = 0 var right = sortedList.size - 1 while (left <= right) { val mid = (left + right) / 2 when { sortedList[mid] == target -> return true sortedList[mid] < target -> left = mid + 1 else -> right = mid - 1 } } return false }
O(n) — Linear Time
Here, time grows linearly with input size.fun contains(items: List<Int>, value: Int): Boolean { for (item in items) { if (item == value) return true } return false }
O(n log n) — Log-Linear Time
Typical of efficient sorting algorithms.fun mergeSort(list: List<Int>): List<Int> { if (list.size <= 1) return list val mid = list.size / 2 val left = mergeSort(list.subList(0, mid)) val right = mergeSort(list.subList(mid, list.size)) return merge(left, right) } fun merge(left: List<Int>, right: List<Int>): List<Int> { val merged = mutableListOf<Int>() var i = 0 var j = 0 while (i < left.size && j < right.size) { if (left[i] <= right[j]) merged.add(left[i++]) else merged.add(right[j++]) } merged.addAll(left.drop(i)) merged.addAll(right.drop(j)) return merged }
O(n²) — Quadratic Time
Nested loops, like comparing every pair in a list.fun hasDuplicateBruteForce(items: List<Int>): Boolean { for (i in items.indices) { for (j in i + 1 until items.size) { if (items[i] == items[j]) return true } } return false }
O(2ⁿ) — Exponential Time
Typically seen in recursive brute-force algorithms.fun fibonacci(n: Int): Int { return if (n <= 1) n else fibonacci(n - 1) + fibonacci(n - 2) }
Each of these snippets not only demonstrates a complexity class but also helps you see how patterns emerge — recursion, nesting, iteration, and divide-and-conquer.
Want to dive into space complexity next, or play with optimization tricks like memoization? I’d be delighted to go deeper.
Author: John Rowan
I am a Senior Android Engineer and I love everything to do with computers. My specialty is Android programming but I actually love to code in any language specifically learning new things.Share this:
