Big O Notation

What is Big-O Notation

Language computer scientists use when comparing the performance of algorithms.

It is consist of two parts - time & space.

time Complexity
Space Complexity

• can often trade-off time for space

Most common Characteristics are:

• Quadratic: O(n^2)
• Linear: O(n)
• Constant: O(1)
• Logarithmic: O(logn)

Big-O Complexity Chart

※ bigocheatsheet.com

Hashmap vs. brute

• Hash map is the better solution compared to naive brute force.
• 🍯Tip1 -Hash maps/Dictionaries are your friend.
• for example

1. Hashmap

func commonItemsHash(_ A: [Int], _ B: [Int]) -> Bool {
    var hashA = [Int: Bool]() //O(n)
    for a in A { // O(n)
        hashA[a] = true
    }

    for b in B {
        if hashA[b] == true {
            return true
        }
    }
    return false
}

2. Bruteforce

func commonItemsBrute(_ A: [Int], _ B: [Int]) -> Bool {
    for i in 0..<A.count {
        for j in 0..<B.count {
            if A[i] == B[j] {
                return true
            }
        }
    }
    return false
}

	Hashmap	BruteForce
time Complexity	O(n)	O(n^2)
Space Complexity	O(n)	O(1)