1. O(n)
1
2
3
4
for i := 0; i < n; i++ {
	//statements
}

  1. O(n2)
1
2
3
4
5
6
for i := 0; i < n; i++ {
	for j := 0; j < n; j++ {
		//statements
	}
}

  1. O(n2)
1
2
3
4
5
6
for i := 0; i < n; i++ {
	for j := 0; j < i; j++ {
		//statements
	}
}

Explaination:

i j
0 0
1 1
2 2
… …
n n

So the complexity is : 1 + 2 + 3 + ... + n = n * (n + 1) / 2 = O(n2)

  1. O()
1
2
3
4
5
for i, j := 0, 0; j < n; i++ {
	j += i
	//statements
}

Explaination:

i j
0 0
1 0 + 1
2 0 + 1 + 2
3 0 + 1 + 2 + 3
… …
k 0 + 1 + 2 + 3 + … + k

We need to find the solution for 1 + 2 + 3 + ... + k > n => k >

  1. O()
1
2
3
4
for i := 1; i <= n; i *= 2 {
	//statements
}

Explaination:

We need to find the solution for 2<sup>k</sup> < n => k <

  1. O()
1
2
3
4
for i := n; i >= 1; i /= 2 {
	//statements
}

Explaination:

We need to find the solution for > 1 => k <

  1. O()
1
2
3
4
for i := 0; i * i < n; i++ {
	//statements
}

Explaination:

We need to find the solution for k2 < n => k <

  1. Time complexity for resursion.

a. T(n) = T(n - 1) + 1 => O(n)

1
2
3
4
5
6
7
func x(n int) {
	if (n > 0) {
		return x(n - 1)
	}
	return 1
}

b. T(n) = T(n - 1) + n => O(n2)

1
2
3
4
5
6
7
8
9
10
func x(n int) {
	if (n > 0) {
		for i := 0; i < n; i++ {
			//statements
		}
		return x(n - 1)
	}
	return 1
}

Explaination:

T(n) = T(n - 1) + n = T(n - 2) + (n - 1) + n = T(n - 3) + (n - 2) + (n - 1) + n = … = T(1) + 1 + 2 + 3 + … + n

c. T(n) = T(n - 1) + => O()

1
2
3
4
5
6
7
8
9
10
func x(n int) {
	if (n > 0) {
		for i := 0; i < n; i *= 2 {
			//statements
		}
		return x(n - 1)
	}
	return 1
}

Explaination:

Similar like 8.b, the time complexity will be + + + … + = ≈ n

d. T(n) = 2 * T(n - 1) + 1 => O(2n)

1
2
3
4
5
6
7
8
9
10
func x(n int) {
	if (n > 0) {
		for i := 0; i < n; i *= 2 {
			//statements
		}
		return x(n - 1)
	}
	return 1
}

Explaination:

Similar like 8.b, the time complexity will be T(n) = 2 * T(n - 1) + 1 = 4 * T(n - 2) + 2 + 1 = 8 * T(n - 3) + 4 + 2 + 1 = … = 2n * T(0) + 2n-1 + 2n-2 + … + 4 + 2 + 1 = 2n + 1 - 1 [Geometric Sequence]

e. T(n) = T(n / 2) + 1 => O() [Classic Binary Search]

1
2
3
4
5
6
7
8
func x(n int) {
	if (n > 1) {
		//statements
		return x(n/2)
	}
	return 1
}

Explaination:

Similar like 8.b, the time complexity will be T(n) = T(n - 1) + 1 = T(n - 2) + 1 + 1 = … = T() + * 1

f. T(n) = T(n / 2) + n => O(n)

1
2
3
4
5
6
7
8
9
10
func x(n int) {
	if (n > 1) {
		for i := 0; i < n; i++ {
			//statements	
		}
		return x(n/2)
	}
	return 1
}

Explaination:

Similar like 8.3, the time complexity will be T(n) = T(n/2) + n = T(n/4) + n / 2 + n = … = T(n/2k) + n / 2k-1 + … + n / 21 + n / 20 = T(1) + n * (1 / 2k-1 + … + 1 / 21 + 1 / 20) = O(n) [Geometric Sequence]

g. T(n) = 2T(n / 2) + n => O(n)

1
2
3
4
5
6
7
8
9
10
func x(n int) {
	if (n > 1) {
		for i := 0; i < n; i++ {
			//statements	
		}
		return x(n/2)
	}
	return 1
}

Explaination:

Similar like 8.3, the time complexity will be T(n) = 2 * T(n/2) + n = 4 * T(n/4) + n + n = 8 * T(n / 8) + n + n + n = … = 2k * T(n / 2k) + k * n = n * T(1) + * n = O(n)

Now, Let’s take a look at a problem from Leetcode 50. Pow(x, n).

a. Brute-force solution O(n) => template #8.a

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func myPow(x float64, n int) float64 {
	upperBound := n
	if n < 0 {
		upperBound = -n
	}
	ret := 1.0
	for i := 1; i <= upperBound; i++ {
		ret *= x
	}
	if n > 0 {
		return ret
	}
	return 1 / ret
}

Golang Playbook: https://play.golang.org/p/YxdrpGt-VXT

b. Let’s try recursive solution I O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func recursivePow(x float64, n int) float64 {
	if n == 0 {
		return 1
	}
	return recursivePow(x, n-1) * x
}

func myPow(x float64, n int) float64 {
	upperBound := n
	if n < 0 {
		upperBound = -n
	}

	ret := recursivePow(x, upperBound)
	if n > 0 {
		return ret
	}
	return 1 / ret
}

Golang Playbook: https://play.golang.org/p/O_MPA_gORmA

NOTE: This is still O(n) since the recursivePow was invoked n times

c. Let’s try recursive solution II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

func recursivePow(x float64, n int) float64 {
	if n == 0 {
		return 1
	}
	if n%2 == 0 {
		return recursivePow(x, n/2) * recursivePow(x, n/2)
	}
	return recursivePow(x, n/2) * recursivePow(x, n/2) * x
}

func myPow(x float64, n int) float64 {
	upperBound := n
	if n < 0 {
		upperBound = -n
	}
	ret := recursivePow(x, upperBound)
	if n > 0 {
		return ret
	}
	return 1 / ret
}

Golang Playbook: https://play.golang.org/p/m2azp6-WuLF

NOTE: Actually, this idea comes as a Divide & Concor solution, but if you count how many times recursivePow are invoked, you will find that it’s still O(n). You can consider the input as a BST’s root node, so our target is to get the nodes number. It will be n.

d. Optimized cached recursive solution III O() => Template #6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

func recursivePow(x float64, n int) float64 {
	if n == 0 {
		return 1
	}
	ret := recursivePow(x, n/2)
	if n%2 == 0 {
		return ret * ret
	}
	return ret * ret * x
}

func myPow(x float64, n int) float64 {
	upperBound := n
	if n < 0 {
		upperBound = -n
	}
	ret := recursivePow(x, upperBound)
	if n > 0 {
		return ret
	}
	return 1 / ret
}

Golang Playbook: https://play.golang.org/p/lzC2k6QgLlF

The only difference between c and d is we cached the result of the function call recursivePow. This will be similar like the binary search, each time we save half of the computation time.

[Refs]