Arrays and strings
Arrays and strings are the structures that most interview-style problems start with, so it helps to know what each common operation costs. Here n is the array's size or the string's length.
Array operations
- Reading or writing
arr[i]:O(1). The element's location is computed fromi. arr.size:O(1).- Finding a value with
indexOforcontains:O(n), because the array is scanned from the start. - Copying with
copyOf()orcopyOfRange(from, to): proportional to the number of elements copied. - Sorting:
O(n log n). - Inserting or deleting in the middle: an array has a fixed size, so you build a new one:
O(n).
String operations
s.lengthands[i]:O(1).s.substring(a, b): it creates a new string, so it costs the length of the piece.s.reversed(),s.uppercase(),s.split(","),s.toCharArray():O(n).s.contains(t)ands.indexOf(t): a scan,O(n)for a single character and up toO(n × m)for a texttof lengthm.s == t: compares character by character, so up toO(n).
Strings are immutable
A Kotlin String can't be changed after it is created. s + t, replace and uppercase() all produce new strings and leave the original untouched. That has a consequence for loops:
var s = ""
for (i in 0 until n) {
s += "ab"
}
Each += builds a new string by copying everything already in s. The copies get longer with every pass, so the total work is about 2 + 4 + 6 + ... + 2n characters, which is O(n²). A StringBuilder keeps one growable buffer instead:
val sb = StringBuilder()
for (i in 0 until n) {
sb.append("ab")
}
val s = sb.toString()
Each append is amortized O(1), so the loop is O(n). To change one character, copy the string into a CharArray with toCharArray(), assign to the array, and build a string back with String(chars). For "hello", setting position 0 to 'j' gives "jello".
Logarithms
A logarithm answers the question: how many times can you halve n before you reach 1? That count is log₂ n, usually written log n in Big O. A loop that halves its remaining work on every pass runs O(log n) times:
fun halvings(n: Int): Int {
var x = n
var steps = 0
while (x > 1) {
x /= 2
steps++
}
return steps
}
With integer division, the results are:
| n | halvings(n) |
|---|---|
| 8 | 3 |
| 1,000 | 9 |
| 1,000,000 | 19 |
| 1,000,000,000 | 29 |
A billion values need about 30 halvings. This is why O(log n) is so valuable: the input can grow enormously and the step count barely moves. (The function returns the rounded-down value of log₂ n; for a million that is 19, while the exact value is just under 20.)
Binary search
The classic O(log n) algorithm is binary search on a sorted array. Compare the target with the middle element; the answer is in only one half, so discard the other half and repeat. Counting the comparisons on the sorted array 0, 1, 2, ..., n - 1, searching for the last element, a linear scan and a binary search compare like this:
| n | linear scan | binary search |
|---|---|---|
| 1,000 | 1,000 | 10 |
| 1,000,000 | 1,000,000 | 20 |
The standard library offers binarySearch on arrays and lists. It requires the data to be sorted already; on unsorted data its answer is meaningless. Sorting first costs O(n log n), so it only pays off when you search many times.
Other places logarithms show up
- Sorting. Efficient sorts split the data in half repeatedly (about
log nlevels) and doO(n)work per level, givingO(n log n). - Counting digits. The number of digits of
nis aboutlog₁₀ n, so a loop that divides by 10 until it reaches 0 isO(log n).
The base of the logarithm does not matter in Big O, because changing the base only multiplies by a constant, and Big O ignores constants.
Key takeaways
- Array and string indexing and length are
O(1); searching and copying areO(n). - Strings are immutable, so repeated
+=in a loop isO(n²); use aStringBuilder. O(log n)comes from halving: binary search on sorted data needs about 20 steps for a million elements.