Let the functions below have the following runtime complexity. c i is some const
ID: 670591 • Letter: L
Question
Let the functions below have the following runtime complexity. ci is some constant factor. All questions
in this assignment refer to these functions.
f1(n) = ~c1
f2(n) = ~c2lg(n)
f3(n) = ~c3n
f4(n) = ~c4nlg(n)
f5(n) = ~c5n2
f6(n) = ~c6n2lg(n)
f7(n) = ~c7n3
f8(n) = ~c8 2n
1 - Are the following true or false according to the definitions of O, Omega, Theta
a) f1(n) is O(n2) T F
b) f5(n) is O(n2) T F
c) f6(n) is O(n2) T F
d) f5(n) is Omega(n2) T F
e) f3(n) is Omega(n2) T F
f) f8(n) is Omega(n2) T F
g) f5(n) is Theta(n2) T F
h) f6(n) is Theta(n2) T F
i) f4(n) is Theta(n2) T F
2 – What is the complexity of the following algorithms composed of calls to the functions above? For
each algorithm below provide
– the number of operations in terms of n (e.g. f(n) = 10c7n3 + 100c4nlg(n))
– a tight bound for Big O (e.g. O(n3))
– the tilde value (e.g. ~ 10c7n3)
a) f3(n); f7(n); f5(n);
b) for (int i=0; i<1000000; i++) { f1(n); }
c) for (int i=0; i<n; i++) { f2(n); f6(n); f3(n); }
d) for (int i=0; i<n; i++) {
for (int j=i+1; j<1000; j++) {
f1(n);
f4(n);
f1(n);
}
}
e) for (int i=0; i<n; i++) {
for (int j=i+1; j<n; j++) {
f3(n);
}
}
for (int i=0; i<5; i++) {
f6(n)
}
f) for (int i=0; i<2; i++) {
f8(n)
}
f7(n);
g) for (int i=0; i<10000000; i++) {
f6(n)
}
f7(n);
3 – A given algorithm takes 0.1 ms for n=10. How long should we expect this algorithm to take for
– n = 20
– n = 200
(calculate for both those values)
if the algorithm in question is:
a) f1(n)
b) f2(n)
c) f3(n)
d) f4(n)
e) f5(n)
f) f6(n)
g) f7(n)
h) f8(n)
Explanation / Answer
Given statements:
f1(n) = ~c1 Constant.
f2(n) = ~c2 lg(n) Logarithmic.
f3(n) = ~c3 n Linear.
f4(n) = ~c4 n lg(n) Linear Logarithmic
f5(n) = ~c5 n2 Quadratic
f6(n) = ~c6 n2 lg(n) Quadratic Logarithmic
f7(n) = ~c7 n3 Cubic
f8(n) = ~c8 2n Exponential.
Usually, when representing efficiencies of a function using Asymptotic notations:
O stands for the function f has a maximum of O(g). Worst Case representation.
Omega stands for the function f has a minimum of Omega(g). Best Case representation.
Theta stands for the function f has exactly of Theta(g). Average Case representation.
1 - Are the following true or false according to the definitions of O, Omega, Theta
a) f1(n) is O(n2) T F True
b) f5(n) is O(n2) T F True
c) f6(n) is O(n2) T F False
d) f5(n) is Omega(n2) T F True
e) f3(n) is Omega(n2) T F False
f) f8(n) is Omega(n2) T F True
g) f5(n) is Theta(n2) T F True
h) f6(n) is Theta(n2) T F False
i) f4(n) is Theta(n2) T F False
2 – What is the complexity of the following algorithms composed of calls to the functions above? For
each algorithm below provide
– the number of operations in terms of n (e.g. f(n) = 10c7n3 + 100c4nlg(n))
– a tight bound for Big O (e.g. O(n3))
– the tilde value (e.g. ~ 10c7n3)
a) f3(n); No. of operations: c3 n Bound O(n) ~c3 n
f7(n); No. of operations: c7 n3 Bound O(n3) ~c7 n3
f5(n); No. of operations: c5 n2 Bound O(n2) ~c5 n2
b) for (int i=0; i<1000000; i++) { f1(n); } No. of operations: 1000000 c1 Bound O(1) ~1000000 c1
c) for (int i=0; i<n; i++) { f2(n); f6(n); f3(n); } No. of operations: c2 log(n) + c6 n2 log(n) + c3 n Bound O(n2logn) ~c2 log(n) + c6 n2 log(n) + c3 n
d) for (int i=0; i<n; i++) {
for (int j=i+1; j<1000; j++) {
f1(n);
f4(n);
f1(n);
}
} No. of operations: (500,500 - (n*n+1)/2)(2 * c1 + c4 n log(n)) O(n3logn) ~(500,500 - (n*n+1)/2)(2 * c1 + c4 n log(n))
e) for (int i=0; i<n; i++) {
for (int j=i+1; j<n; j++) {
f3(n);
}
}
for (int i=0; i<5; i++) {
f6(n)
} No. of operations: n2 c3 n + 5 * c6 n2 log(n) O(n3) ~n2 c3 n + 5 * c6 n2 log(n).
f) for (int i=0; i<2; i++) {
f8(n)
}
f7(n); No. of operations: (2 * c8 2n )+ (c7 n3) O(2n) ~ (2 * c8 2n )+ (c7 n3)
g) for (int i=0; i<10000000; i++) {
f6(n)
}
f7(n); No. of operations: 10000000 * c6 n2 log(n) + c7 n3. O(n3). ~10000000 * c6 n2 log(n) + c7 n3.
3 – A given algorithm takes 0.1 ms for n=10. How long should we expect this algorithm to take for
– n = 20
– n = 200
(calculate for both those values)
if the algorithm in question is:
a) f1(n) c1. Constant. For this the time required to run the algorithm is not based on n.
b) f2(n) c2 log(n) log 10 = ~3.32. To execute 3.32 instructions the time required is 0.1 ms. When n = 20. log 20 = 4.32, when n = 200, log 200 = 7.64. Therefore to execute 4.32 instructions the time required is: 0.13 ms. and to execute 7.64 instructions the time required is: 0.23 ms.
c) f3(n) c3 n = ~10. To execute 10 instructions the time required is 0.1 ms. Therefore to execute 20 instructions the time required is: 0.2 ms, and to execute 200 instructions the time required is: 20 ms.
d) f4(n) c4 n log n. 10 * log 10 = ~33.2. To execute 33.2 instructions the time required is 0.1 ms. When n = 20, 20 * log 20 = 86.4, when n = 200, 200 * log 200 = 1528. Therefore to execute 86.4 instructions the time required is: 0.26 ms. and to execute 1528 instructions the time required is: 4.6 ms.
e) f5(n) c5 n2. 102 = 100. To execute 100 instructions the time required is 0.1 ms. When n = 20, 202 = 400, when n = 200, 2002 = 40000. Therefore to execute 400 instructions the time required is: 0.4 ms. and to execute 40000 instructions the time required is: 40 ms.
f) f6(n) c6 n2 log(n). 102 log10 = 332.19. To execute 332.19 instructions the time required is 0.1 ms. When n = 20, 202 * log 20 = 1728.77, when n = 200, 2002 * log 200 = 305754.24. Therefore to execute 1728.77 instructions the time required is: 0.52 ms. and to execute 305754.24 instructions the time required is: 92.04 ms.
g) f7(n) c7 n3. 103 = 1000. When n = 20, 203 = 8000, and when n = 200, 2003 = 8000000. To execute 1000 instructions the time required is: 0.1, to execute 8000 instructions the time required is: 0.8 ms. and to execute 8000000 instructions the time required is: 800 ms.
h) f8(n) c8 2n. 210 = 1024. When n = 20, 220 = 1048576, and when n = 200, 2200 = 1.6 e 60. To execute 1024 instructions the time required is: 0.1, to execute 1048576 instructions the time required is: 102.4 ms, and to execute 1.6 e 60 instructions the time required is: 1.56 e 56.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.