How to determine the time complexity of a function that finds the first element in one array that is missing in another?

To determine the time complexity of a function that finds the first element in array A missing in array B, analyze the algorithm:

1. If for each element in A, you check its presence in B by iteration (e.g., a loop), then for each element in A, you perform a search in B — this is O(n) for each element, where n is the size of B. If the size of A is m, the total complexity will be O(m * n).

2. If you first create a data structure for quick lookup, such as a HashSet from elements of B (in O(n)), then checking for an element's presence is O(1) on average. The overall algorithm then is:

• Create a HashSet from B — O(n)
• Iterate over A and check presence in HashSet — O(m)

Total time complexity — O(m + n).

Example in Kotlin:

fun findFirstMissing(a: List<Int>, b: List<Int>): Int? {
    val setB = b.toHashSet() // O(n)
    for (element in a) { // O(m)
        if (element !in setB) {
            return element
        }
    }
    return null
}

Thus, the time complexity depends on the implementation and can range from O(m * n) to O(m + n).