ALGORITHMS AND COMPLEXITY
HIT 220 Algorithms and Complexity
Complexity Calculation Tutorial, week 2
N = 200
(a) 7.6439 microseconds
(a) 7.6439 microseconds (b) 200 microseconds OR 0.2 milliseconds
Tip: (1 microsecond is .001 milliseconds)
(a) 7.6439 microseconds (b) 200 microseconds OR 0.2 milliseconds (c) 1528.78 microseconds OR 1.52878 milliseconds
Tip: (1 microsecond is .001 milliseconds)
(a) 7.6439 microseconds (b) 200 microseconds OR 0.2 milliseconds (c) 1528.78 microseconds OR 1.52878 milliseconds (d) 40,000 microseconds OR 40 milliseconds
Tip: (1 microsecond is .001 milliseconds)
(a) 7.6439 microseconds (b) 200 microseconds OR 0.2 milliseconds (c) 1528.78 microseconds OR 1.52878 milliseconds (d) 40,000 microseconds OR 40 milliseconds (e) 8,000,000 microseconds OR 8,000 milliseconds OR 8 seconds
Tip: (1 microsecond is .001 milliseconds)
(a) 7.6439 microseconds (b) 200 microseconds OR 0.2 milliseconds (c) 1528.78 microseconds OR 1.52878 milliseconds (d) 40,000 microseconds OR 40 milliseconds (e) 8,000,000 microseconds OR 8,000 milliseconds OR 8 seconds (f) 1.606938 x 1060 microseconds OR a helluva lot of seconds (1.606938 x 1057)
Tip: (1 microsecond is .001 milliseconds)
2(a)
1 +
1 subtraction
2(a)
1 + (n-4)
Executes loop n-4 times
1 subtraction
2(a)
1 + (n-4)(4)
Executes loop n-4 times
1 subtraction
2 multiplications + 1 addition + 1 subtraction
2(a)
1 + (n-4)(4)
= 4n-16+1
= 4n-15
= O(n)
Executes loop n-4 times
1 subtraction
2 multiplications + 1 addition + 1 subtraction
2(b)
(n-2)
Loop executes n-2 times
2(b)
(n-2)(1)
Loop executes n-2 times 1 comparison
2(b)
(n-2)(1)
= n-2
= O(n)
Loop executes n-2 times 1 comparison
2(c)
1 +
1 division in initialization
2(c)
1 + (n/2)
1 division in initialization
Loop executes n/2 times
2(c)
1 + (n/2)(1)
1 division in initialization
Loop executes n/2 times
1 subtraction
2(c)
1 + (n/2)(1)
= 1 + (n/2)
= ½ n + 1
= O(n)
1 division in initialization
Loop executes n/2 times
1 subtraction
2(c)
1 + (n/2)(1)
= 1 + (n/2)
= ½ n + 1
= O(n)
1 division in initialization
Loop executes n/2 times
1 subtraction
N 2 4 6 8 10
Inner loop executions
1 2 3 4 5
2(c) 1 division in initialization
Loop executes n/2 times
1 subtraction
N 2 4 6 8 10
Inner loop executions
1 2 3 4 5
2(d)
n
Loop_1 executes n times
2(d)
n(1)
Loop_1 executes n times
1 multiplication
2(d)
n(1 + 2n)
Loop_1 executes n times
Loop_2 executes 2n times
1 multiplication
2(d)
n(1 + 2n(3))
Loop_1 executes n times
Loop_2 executes 2n times
2 multiplications + 1 addition
1 multiplication
2(d)
n(1 + 2n(3))
= n(1 + 6n)
= 6n2 + n
= O(n2)
Loop_1 executes n times
Loop_2 executes 2n times
2 multiplications + 1 addition
1 multiplication
2(e) Loop executes n-1 times
2(e) Loop executes n-1 times
Inner loop executes ??? times
2(e) Loop executes n-1 times
Inner loop executes ??? times
Summation notation and a couple rules can help us out here:
a) b)
2(e) Loop executes n-1 times
Inner loop executes ??? times
a) b)
2(e) Loop executes n-1 times
Inner loop executes ??? times
a) b)
2(e) Loop executes n-1 times
Inner loop executes ??? times
a) b)
2(e) Loop executes n-1 times
Inner loop executes ??? times
a) b)
2(e) Loop executes n-1 times
Inner loop executes ??? times
a) b)
2(e) Loop executes n-1 times
Inner loop executes ??? times
a) b)
2(e) Loop executes n-1 times
Inner loop executes ??? times
a) b)
2(e) Loop executes n-1 times
Inner loop executes ??? times
a) b)
2(e) Loop executes n-1 times
Inner loop executes ??? times
a) b)
2(e) Loop executes n-1 times
Inner loop executes ??? times
a) b)
2(e) Loop executes n-1 times
Inner loop executes ??? times
a) b)
= O(n2)
2(f)
2(f) Outer loop executes n times
2(f) Outer loop executes n times
Inner loop executes ??? times
a) b)
2(f) Outer loop executes n times
Inner loop executes ??? times
1 comparison in inner loop
a) b)
2(f) Outer loop executes n times
Inner loop executes ??? times
1 comparison in inner loop
a) b)
2(f) Outer loop executes n times
Inner loop executes ??? times
1 comparison in inner loop
a) b)
2(f) Outer loop executes n times
Inner loop executes ??? times
1 comparison in inner loop
a) b)
2(f) Outer loop executes n times
Inner loop executes ??? times
1 comparison in inner loop
a) b)
2(f) Outer loop executes n times
Inner loop executes ??? times
1 comparison in inner loop
a) b)
2(f) Outer loop executes n times
Inner loop executes ??? times
1 comparison in inner loop
a) b)
2(f) Outer loop executes n times
Inner loop executes ??? times
1 comparison in inner loop
a) b)
2(f) Outer loop executes n times
Inner loop executes ??? times
1 comparison in inner loop
a) b)
2(f) Outer loop executes n times
Inner loop executes ??? times
1 comparison in inner loop
a) b)
= O(n2)
2(g) Outer loop executes n times
2(g) Outer loop executes n times
Inner loop executes ??? times
a) b)
2(g) Outer loop executes n times
Inner loop executes ??? times
a) b)
2(g) Outer loop executes n times
Inner loop executes ??? times
a) b)
2(g) Outer loop executes n times
Inner loop executes ??? times
a) b)
2(g) Outer loop executes n times
Inner loop executes ??? times
a) b)
2(g) Outer loop executes n times
Inner loop executes ??? times
a) b)
2(g) Outer loop executes n times
Inner loop executes ??? times
a) b)
2(g) Outer loop executes n times
Inner loop executes ??? times
a) b)
2(g) Outer loop executes n times
Inner loop executes ??? times
a) b)
2(g) Outer loop executes n times
Inner loop executes ??? times
a) b)
= O(n2)
(a) = log2(10 3) = 3log2(10) = 3 * 3.32 = 9.96
(a) = log2(10 3) = 3log2(10) = 3 * 3.32 = 9.96
(b) = log2(10 6) = 6log2(10) = 6 * 3.32 = 19.92
(a) = log2(10 3) = 3log2(10) = 3 * 3.32 = 9.96
(b) = log2(10 6) = 6log2(10) = 6 * 3.32 = 19.92
(c) = log2(10 12) = 12log2(10) = 12 * 3.32 = 39.84
(a) 2, because: log2(n 2) = 2log2(n)
(b) 10, because: log2(n 10) = 10log2(n)
(c) 5, because: 2log2(10) * 5 = 10log2(10)