CS Basics: Big-O, Memory, Threading & Networking

Real-world analogy

What is it?

Computer science fundamentals are the shared vocabulary of all software engineers. Big-O lets you predict and reason about performance. Memory models explain OutOfMemoryErrors and ANRs. Threading models are the foundation for coroutines. Networking fundamentals explain every Retrofit call under the hood. Senior mobile engineers are expected to speak this language fluently in system design and code review discussions.

Real-world relevance

When a senior engineer at FieldBuzz reviewed a sync algorithm that iterated all local records for every incoming server record to check for duplicates — a clear O(n^2) pattern causing 30-second freezes for large datasets — they refactored it to build a HashSet of local IDs first (O(n)), then check membership for each server record (O(1) each), bringing total complexity from O(n^2) to O(n) and reducing sync time from 30s to under 1s.

Key points

• O(1) — Constant Time — The operation takes the same time regardless of input size. HashMap.get() is O(1) average — you compute a hash, go directly to the bucket. Array index access arr[i] is O(1). These are the fastest operations; prefer them in hot paths.
• O(n) — Linear Time — Time grows proportionally with input size. Scanning a list to find an element is O(n). Building a HashMap from a list is O(n). Acceptable for most operations but avoid O(n) work inside loops — that creates O(n^2).
• O(log n) — Logarithmic Time — Time grows slowly as input doubles. Binary search on a sorted array is O(log n) — each step halves the search space. A sorted list of 1 billion items needs only ~30 comparisons. TreeMap operations are O(log n). This is the sweet spot for search.
• O(n^2) — Quadratic Time — Time grows as the square of input size. Nested loops over the same collection are O(n^2). Bubble sort is O(n^2). Fine for n<1000 but catastrophic for large datasets. Always ask: can I replace the inner loop with a HashMap lookup to bring this to O(n)?
• O(n log n) — Linearithmic Time — The best possible time for comparison-based sorting. Merge sort, heap sort, and Kotlin's sort() are all O(n log n). When you see 'sort then process', the sort dominates with O(n log n).
• Space Complexity — How much extra memory an algorithm uses as input grows. An in-place sort uses O(1) extra space. A HashMap storing all elements uses O(n) space. Recursion uses O(depth) stack space — deep recursion can cause StackOverflow on Android (default stack ~8KB). Always consider space when optimizing time.
• Stack vs Heap Memory — Stack: fast, automatically managed, stores local variables and function call frames. Limited size (~8KB per thread on Android). Heap: large, GC-managed, stores all objects (List, HashMap, Bitmap). Stack overflow = too deep recursion. OutOfMemoryError = heap exhausted, usually from Bitmap loading or large caches without limits.
• Process vs Thread vs Coroutine — Process: isolated OS unit with its own memory space. Thread: lightweight unit within a process sharing memory — preemptive scheduling, blocking is expensive. Coroutine: user-space cooperative concurrency — suspends instead of blocking, thousands can run on a handful of threads. Android's main thread = UI thread; blocking it causes ANRs.
• TCP/IP and HTTP Basics — TCP: reliable, ordered byte stream — establishes connection via 3-way handshake (SYN, SYN-ACK, ACK). HTTP/1.1 uses one request per connection. HTTP/2 multiplexes many requests over one TCP connection, reducing latency significantly. HTTPS adds TLS on top of TCP.
• DNS Resolution — DNS converts 'api.myapp.com' to an IP address. Lookup order: local cache → OS cache → router → ISP resolver → root nameserver → authoritative server. First request is slow (50-200ms). Subsequent requests use TTL-based caching. OkHttp's DnsOverHttps can bypass ISP censorship and speed up resolution.
• REST Constraints — REST is an architectural style, not a protocol. Key constraints: stateless (server holds no session state), client-server separation, uniform interface (standard HTTP methods + status codes), cacheable responses, layered system. A truly RESTful API uses nouns for resources (not verbs), uses GET/POST/PUT/DELETE correctly, and returns appropriate status codes (200/201/400/401/404/500).
• HTTP Status Codes for Mobile Engineers — 200 OK, 201 Created, 204 No Content. 400 Bad Request (fix your request), 401 Unauthorized (re-authenticate), 403 Forbidden (you are authenticated but not allowed), 404 Not Found, 409 Conflict (duplicate). 500 Internal Server Error (server bug, retry), 503 Service Unavailable (retry with backoff). Knowing these lets you write precise error handling.

Code example

// Big-O demonstration in Kotlin

// O(1) — HashMap lookup
fun hasElement(map: HashMap<String, Int>, key: String): Boolean {
    return map.containsKey(key) // O(1) average
}

// O(n) — Linear scan
fun findFirst(list: List<Int>, target: Int): Int {
    for (i in list.indices) { // O(n)
        if (list[i] == target) return i
    }
    return -1
}

// O(n^2) — Naive duplicate check
fun hasDuplicatesNaive(list: List<Int>): Boolean {
    for (i in list.indices) {         // O(n)
        for (j in i + 1 until list.size) { // O(n)
            if (list[i] == list[j]) return true // O(n^2) total
        }
    }
    return false
}

// O(n) — Optimized duplicate check with HashSet
fun hasDuplicatesFast(list: List<Int>): Boolean {
    val seen = HashSet<Int>() // O(n) space
    for (item in list) {      // O(n) time
        if (!seen.add(item)) return true // HashSet.add returns false if already present
    }
    return false
}

// O(log n) — Binary search
fun binarySearch(sortedList: List<Int>, target: Int): Int {
    var left = 0
    var right = sortedList.size - 1
    while (left <= right) {
        val mid = left + (right - left) / 2 // avoid integer overflow
        when {
            sortedList[mid] == target -> return mid
            sortedList[mid] < target -> left = mid + 1
            else -> right = mid - 1
        }
    }
    return -1
}

// Space complexity: O(depth) recursion on call stack
fun factorial(n: Int): Long {
    if (n <= 1) return 1
    return n * factorial(n - 1) // O(n) stack frames — risky for large n
}

Line-by-line walkthrough

1. 1. hasDuplicatesNaive uses two nested loops — for every element i, it checks every element j after it. This is n*(n-1)/2 comparisons, which is O(n^2).
2. 2. hasDuplicatesFast creates a HashSet first. HashSet.add() returns false if the element was already present — this replaces the inner loop entirely.
3. 3. The HashSet approach trades O(n) extra space for the set to bring time from O(n^2) to O(n) — classic time-space tradeoff.
4. 4. binarySearch calculates mid as left + (right - left) / 2 not (left + right) / 2 — the latter can overflow Int.MAX_VALUE when left and right are both large.
5. 5. Each iteration of binary search halves the remaining search space — after k iterations, the remaining space is n/2^k. Solving 2^k = n gives k = log2(n).
6. 6. factorial is recursive — each call adds a frame to the call stack. factorial(10000) would overflow Android's thread stack (~8KB). Iterative version uses O(1) stack space.
7. 7. HashMap.containsKey is O(1) average because it computes a hash and goes directly to the bucket. Worst case is O(n) when all keys hash to the same bucket — extremely rare with a good hash function.
8. 8. The binary search returns -1 for not found (following Java convention) — in production Kotlin, returning null or a sealed Result type is more idiomatic than sentinel values.

Spot the bug

fun findCommonElements(listA: List<Int>, listB: List<Int>): List<Int> {
    val result = mutableListOf<Int>()
    for (a in listA) {
        for (b in listB) {
            if (a == b) {
                result.add(a)
            }
        }
    }
    return result
}

// Called with listA.size = 10000, listB.size = 10000

Explain like I'm 5

Fun fact

Hands-on challenge

More resources

• Big-O Cheat Sheet (Big-O Cheat Sheet)
• Android Memory Overview (Android Developers)
• HTTP/2 Explained (Haxx)
• Kotlin Coroutines vs Threads (Kotlin)
• REST Constraints — Roy Fielding Dissertation Summary (RESTful API)