Lesson 7.3 · Answer it
Loops in a row
5 marksYou mark it yourself against the marking points
Each of these two functions takes a whole number n from 1 to 1000 and returns how many times the line total = total + 1 ran (in Java, total = total + 1;).
Function A:
def hours_in(n):
total = 0
for day in range(n):
for h in range(24):
total = total + 1
return total
public static int hoursIn(int n) {
int total = 0;
for (int day = 0; day < n; day++) {
for (int h = 0; h < 24; h++) {
total = total + 1;
}
}
return total;
}
Function B:
def two_parts(n):
total = 0
for i in range(n):
total = total + 1
for i in range(n):
for j in range(n):
total = total + 1
return total
public static int twoParts(int n) {
int total = 0;
for (int i = 0; i < n; i++) {
total = total + 1;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
total = total + 1;
}
}
return total;
}
(a) State the value function A returns when n is 10. [1]
(b) State the Big O complexity of function A. [1]
(c) Function A has a loop inside a loop. Explain why it does not have the complexity O(n²). [1]
(d) State the Big O complexity of function B. [1]
(e) Explain why the first loop in function B does not appear in your answer to (d). [1]
[5]