Algorithm efficiency and Big O notation

State the time complexity in Big-O notation of each code fragment, where n = len(items).

(a)

for i in range(n):
    for j in range(n):
        count += 1

[1]

(b)

i = n
while i > 1:
    i = i // 2

[1]

(c)

total = 0
for x in items:
    total += x

[1]

(d) Outline why the fragment in (b) is much more efficient than the fragment in (c) for very large n. [1]

Two algorithms check whether a list of n integers contains duplicates. Every integer in the list is between 0 and 99 999.

Algorithm A

def has_dup_a(nums):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] == nums[j]:
                return True
    return False

Algorithm B

def has_dup_b(nums):
    seen = [False] * 100000
    for x in nums:
        if seen[x]:
            return True
        seen[x] = True
    return False

(a) State the worst-case time complexity of Algorithm A and justify your answer. [2]

(b) Calculate the number of comparisons nums[i] == nums[j] Algorithm A makes in the worst case when n = 10 000. [1]

(c) State the worst-case time complexity of Algorithm B in terms of n. [1]

(d) Describe one disadvantage of Algorithm B compared with Algorithm A. [1]

(e) Identify which algorithm you would recommend for n = 10 000 and give a reason. [1]

A developer says: "My new search algorithm has a time complexity of O(n) and a space complexity of O(1)."

(a) Define the term time complexity. [1]

(b) Outline what a space complexity of O(1) means for this algorithm. [1]

(c) Big O notation usually describes the worst case. Outline why the worst case is more useful to a developer than the best case. [1]

(d) State one operation on a Python list (or Java array) of n items that has a time complexity of O(1). [1]

The graph shows how the number of steps taken by four algorithms, P, Q, R and S, grows as the input size n increases.

(a) Identify the curve that represents each of these time complexities: O(1), O(log n), O(n) and O(n²). [2]

(b) State which of the four algorithms is the least scalable. [1]

(c) Identify one standard algorithm whose worst-case time complexity matches curve P. [1]

A school's timetabling program sorts student records. A tester measures the time taken for different numbers of records. The results are shown below.

(a) Deduce the time complexity of the sorting algorithm in Big O notation. Justify your answer using the data. [2]

(b) Calculate the time the program would be expected to take for 40 000 records. [1]

(c) Suggest one reason why the actual time measured for 40 000 records might differ from your answer to (b). [1]

A programmer counts the basic operations performed by a function that processes a list of n items and finds that the total is

(a) State the time complexity of the function in Big O notation. [1]

(b) Calculate the percentage of the total operations that come from the $3n^2$ term when $n = 1000$. Give your answer to 3 significant figures. [2]

(c) Using your answer to (b), explain why constants and lower-order terms are ignored in Big O notation. [1]

In each fragment below, count starts at 0 and n is a positive integer.

Fragment A

for i in range(n):
    for j in range(i):
        count = count + 1

Fragment B

for i in range(n):
    count = count + 1
for k in range(n):
    count = count + 1

Fragment C

for i in range(n):
    for j in range(10):
        count = count + 1

Fragment D

i = 1
while i < n:
    for j in range(n):
        count = count + 1
    i = i * 2

(a) For n = 16, determine the final value of count for Fragment A and for Fragment D. [2]

(b) State the time complexity in Big O notation of each of the four fragments. [3]

(c) A student says that Fragment C must be O(n²) because it contains a nested loop. Explain why the student is wrong. [1]

A fitness tracker stores the last n heart-rate readings in a list a. Two versions of a function reverse the order of the readings.

Version 1

def reverse_copy(a):
    result = []
    for i in range(len(a) - 1, -1, -1):
        result.append(a[i])
    return result

Version 2

def reverse_in_place(a):
    left = 0
    right = len(a) - 1
    while left < right:
        temp = a[left]
        a[left] = a[right]
        a[right] = temp
        left = left + 1
        right = right - 1

(a) Determine how many times the body of the while loop in Version 2 runs when the list holds 1 000 000 readings. [1]

(b) State the time complexity of each version. [1]

(c) Compare the space complexity of the two versions. [2]

(d) The tracker has very little RAM. Justify which version should be used on the tracker. [1]

A national exam board stores 1 000 000 unsorted candidate records in a list. Staff need to look up candidates by their candidate number.

(a) State the maximum number of comparisons needed to find a record using a linear search. [1]

(b) If the list were sorted, calculate the maximum number of comparisons needed by a binary search. [1]

(c) Sorting the list first with a bubble sort takes $\frac{n(n-1)}{2}$ comparisons. Calculate this number for $n = 1\,000\,000$. [1]

(d) Using your answers, discuss whether the exam board should sort the list with a bubble sort and then use binary search, or continue to use linear search. [3]

The recursive functions below are written in Python. total(items, 0) returns the sum of a list and power(x, n) returns $x^n$ for a whole number $n \ge 0$.

def total(items, i):
    if i == len(items):
        return 0
    return items[i] + total(items, i + 1)


def power(x, n):
    if n == 0:
        return 1
    half = power(x, n // 2)
    if n % 2 == 0:
        return half * half
    return half * half * x

(a) State how many times total is called, including the first call, when total([4, 7, 1, 9], 0) is executed. [1]

(b) State the time complexity of total for a list of n items. [1]

(c) Explain why total has a space complexity of O(n), even though it creates no new lists. [2]

(d) Determine how many times power is called, including the first call, when power(2, 1000) is executed, and hence state its time complexity in terms of n. [2]