Big-O & Complexity on Mobile

What is Big-O?

Big-O notation describes how an algorithm’s work grows as the input gets bigger. It ignores constants and focuses on the shape of the growth, so you can compare approaches. It answers: “if my list goes from 100 to 10,000 items, does my code get 100× slower or 10,000× slower?”

The common complexities (best to worst)

• O(1) constant — same time regardless of size. Hash map lookup. The gold standard.
• O(log n) logarithmic — grows very slowly. Binary search.
• O(n) linear — grows with the input. A single loop over a list.
• O(n log n) — good sorting algorithms.
• O(n²) quadratic — a loop inside a loop. Dangerous on big lists.
• O(2ⁿ) exponential — avoid; only tiny inputs.

Why mobile developers must care

That O(n²) curve is the enemy of a smooth app. To render at 60fps you have ~16ms per frame. An O(n²) operation over a list of 1,000 items is a million steps — easily blowing the budget and dropping frames. The same work on a flagship might be fine but stutters badly on a budget phone.

Reading complexity from code

// O(n): one loop
for (item in items) { process(item) }

// O(n²): nested loop — watch out!
for (a in items) {
    for (b in items) {
        if (a.id == b.id) { ... }
    }
}

// O(1): direct lookup
val user = userMap[id]

A quick rule of thumb: each nested loop multiplies; a hash lookup or array index is constant; halving the search space each step is logarithmic.

Time vs space complexity

Big-O also describes memory (space complexity), which is critical on mobile. Sometimes you trade space for time: a hash map uses more memory but makes lookups O(1). On a memory-constrained phone, you must balance both — a faster algorithm that doubles memory may get your app killed by the OS.

Practical mobile takeaways

• Avoid nested loops over large UI data — especially during scrolling.
• Prefer hash maps/sets for membership checks and lookups.
• Keep heavy O(n)+ work off the main thread.
• Measure on real low-end devices; Big-O predicts trends, profiling confirms reality.

Common mistakes

• Hidden O(n²): calling an O(n) function inside a loop.
• Optimising constants while ignoring the actual complexity.
• Forgetting space complexity until the app runs out of memory.

Summary: Big-O tells you how code scales. On mobile, where you have a 16ms frame budget and limited memory, avoiding O(n²) and choosing O(1)/O(log n) operations keeps the UI smooth — and remember space complexity matters as much as time on a constrained device.