HàPhan 河

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)