Start learning free

KOTLIN · BIG O NOTATION

Time Complexity Guidelines in Kotlin, explained

What constant time means

An operation runs in constant time, written O(1), when the number of steps does not depend on the size of the input. Reading one element out of an array of ten items takes the same effort as reading one out of an array of ten million. The input can grow and the cost stays flat.

Constant doesn't mean "one step" or "instant". It means a fixed amount of work that doesn't scale with n. A function that does 5 additions and a function that does 500 are both O(1), as long as those numbers don't change when the input grows.

Operations that are O(1) in Kotlin

val arr = intArrayOf(4, 8, 15, 16, 23, 42)

val third = arr[2]            // reading by index
arr[0] = 100                  // writing by index
val count = arr.size          // size of an array
val last = arr[arr.size - 1]  // last element
val total = third + last * 2  // arithmetic on numbers

All of these touch a fixed number of values:

  • Index access. An array stores its elements next to each other, so the position of arr[i] is computed directly from i. Nothing is searched.
  • size and length. IntArray.size, List.size and String.length are stored values, not something recounted on each call.
  • Arithmetic and comparisons on Int, Long and Double values.
  • Reading the first or last element of an array or list through its index.
  • Appending to a MutableList with add(x) takes constant time on average. Now and then the list has to grow its storage, which is a bigger step, but spread over many appends the average cost per append is constant. This is called amortized constant time.
  • Looking up a key in a HashMap or HashSet (map[key], key in set) is constant time on average.

A function that is O(1)

fun first(nums: IntArray): Int = nums[0]

fun swapEnds(nums: IntArray) {
    val tmp = nums[0]
    nums[0] = nums[nums.size - 1]
    nums[nums.size - 1] = tmp
}

first does a single read. swapEnds does two reads and two writes, and the count is the same whether nums holds 3 elements or 3 million. Both are O(1) in time, and both use O(1) extra space: swapEnds needs only the one variable tmp.

Constant, not necessarily small

A loop does not make a function slow, if its count is fixed:

fun sumFirstThree(nums: IntArray): Int {
    var total = 0
    for (i in 0 until 3) {
        total += nums[i]
    }
    return total
}

The loop runs exactly 3 times for any array, so this is O(1). The function does assume the array has at least 3 elements; with fewer, nums[i] throws ArrayIndexOutOfBoundsException. Compare it with a loop over nums.indices, whose number of passes grows with the array.

Operations that look constant but aren't

  • Inserting at the front of a list. list.add(0, x) shifts every existing element one place to the right, so it is O(n). The same goes for removeAt(0).
  • contains and indexOf on a list or array. They scan element by element: O(n). The same question on a HashSet is O(1) on average.
  • Copying. toList(), copyOf() and substring copy their data, so the cost grows with the amount copied.
  • Building a string with + inside a loop. Each + creates a new string, copying everything built so far.

How to spot O(1)

  1. Look for loops. If there are none, or each loop has a fixed count, the function is probably constant.
  2. Check each library call you make. A call like sorted(), contains or reversed() hides a loop inside it.
  3. Ask whether the work changes if the input is a thousand times bigger. If not, it is O(1).

Key takeaways

  • O(1) means the cost does not depend on the input size.
  • Index access, size, arithmetic, appending to a list (amortized) and hash lookups (on average) are all constant time.
  • A loop with a fixed count is still constant; a loop over the input is not.
  • Library calls can hide loops, so check what they do.
Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
Start learning free