HàPhan 河

Big O Practice

In previous lesson (https://hapq.me/big-o/), we have learned basic knowledge about Big-O and Time Complexity. But it's not enough, we need to practice carefully to master it. So following the book, I'll try to demonstrate some examples.

Example 1:

func product(_ a: Int, _ b: Int) -> Int {
    var sum: Int = 0
    for i in 0..<b {
        sum += a
    }
    return sum
}

No matter what a is, total assign functions:
1 + b
O(1 + b) = O(b) : Linear time

Example 2:

func power(_ a: Int, _ b: Int) -> Int {
    if b < 0 {
        return 0 //error
    }else if (b == 0) {
        return 1
    }else {
        return a * power(a, b - 1)
    }
}

This function has recursive runtimes follow b value. B will be distracted by 1 until it equals to 0.
So number of called time:
b + 1 -> O(b+1) -> O(b): Linear time

Example 3:

func mod(_ a: Int, _ b: Int) -> Int {
    if (b <= 0) {
        return -1
    }
    let div = a / b
    return a - div * b
}

When b <= 0, just there's one return
when b > 0, number of functions get called is 1 + 1
So time complexity is O(1+1) = O(1) : constant time

Example 4:

//a and b are postivie numbers
func div(_ a: Int, _ b: Int) -> Int {
    var count = 0
    var sum = b
    while (sum <= a) {
        sum += b
        count += 1
    }
    return count
}

This one is little bit tricky.
The worst runtime appear when b is 1, number of assign function is O(1 + 1 + a + a)
so it's O(a), linear time
The best runtime apear when b equals to a, it's O(1 + 1 + 1 + 1), constant time O(1)
I can tell it's O(a/b) runtime for average.

Example 5:

func sqrT(_ n: Int) -> Int {
    return sqrt_helper(n, 1, n)
}

func sqrt_helper(_ n: Int, _ min: Int, _ max: Int) -> Int {
    if max < min {
        return -1
    }
    let guess = (min + max) / 2
    if (guess * guess) == n {
        return guess
    } else if (guess * guess) < n {
        return sqrt_helper(n, guess + 1, max)
    } else {
        return sqrt_helper(n, min, guess - 1)
    }
}

This function try to get square root of a number by adjusting half of sum of 1 and the number. Square root can be higher or lower than half of sum. Number of runtime divided by 2 after each time. So it's O(logn).

Example 6:

func sqrt(_ n: Int) -> Int {
    var it = 1
    while(it * it < n) {
        it = it + 1
    }
    if (it * it) == n {
       return it
    }
    return -1
}

This method increase it by one everytime until it reach Vn, so the time complexity is O(Vn)

Comments