Short description: Analyze time and space complexity of basic iterative algorithms, nested loops, etc.
Relevant notes: Topic A: Big-O Notation and Complexity.
Given an iterative algorithm involving e.g. nested loops, analyze the worst-case asymptotic runtime and/or space usage.
Bound the asymptotic time complexity and space complexity of the following algorithm. In each case, show your work.
1 count_equal_pairs(A):
2 let n = len(A)
3 let s = 0
4 for i = 1 to n:
5 for j = 1 to n:
6 if A[i] == A[j]:
7 s += 1
8 return s
First, we'll write the number of steps each instruction takes.
1 count_equal_pairs(A):
2 let n = len(A) // 1 step
3 let s = 0 // 1 step
4 for i = 1 to n: // 1 step each time executed
5 for j = 1 to n: // 1 step each time executed
6 if A[i] == A[j]: // 1 step each time executed
7 s += 1 // 1 step each time executed
8 return s // 1 step
To count how many times each instruction is executed, we first look at the inner for loop, which covers lines 5-7. In the worst case, line 7 is executed every time, so the loop takes 3 steps every iteration. There are n iterations of the loop. So we can write:
1 count_equal_pairs(A):
2 let n = len(A) // 1 step
3 let s = 0 // 1 step
4 for i = 1 to n: // 1 step each time executed
5 // do at most 3n steps
6 return s // 1 step
The for loop starting in line 3 also runs n times, and we use $3n+1$ operations each time. This gives a total of $n(3n+1) = 3n^2 + n$ operations coming from that for loop:
1 count_equal_pairs(A):
2 let n = len(A) // 1 step
3 let s = 0 // 1 step
4 // do at most 3n^2 + n steps
5 return s // 1 step
The total number of steps is $3n^2 + n + 3 = O(n^2)$ steps, so the final answer is $O(n^2)$.
First, we'll write the amount of space each instruction takes.
1 count_equal_pairs(A):
2 let n = len(A) // 1 space
3 let s = 0 // 1 space
4 for i = 1 to n: // 1 space for i
5 for j = 1 to n: // 1 space for j
6 if A[i] == A[j]: // no additional space
7 s += 1 // no additional space
8 return s // no additional space
We can reuse the space for the variable j each time we initialize the for loop in line 4. So we only need 4 units of space for a total of $4 = O(1)$ space.
To pass, a solution must follow the course requirements for writing.
For time complexity, it should first analyze the inner for loop, finding $O(n)$ operations. It should then analyze the outer for loop, finding $O(n^2)$ operations. It should then note the constant-time operations at the beginning and end, and conclude with an $O(n^2)$ runtime.
For space complexity, it should correctly account for the space used in each line. A solution may pass if it uses a different storage slot for $j$ each time, so that the total space for $j$ is $n$ instead of $1$, although a better implementation is possible.