2.6 Exercises¶
2.6.1 Check your understanding¶
1. Time and space in iteration and recursion¶
Both functions below compute \(1 + 2 + \dots + n\) (assume \(n \ge 1\)). Set n to 4,
follow the program's execution order to answer the questions, and then compare the efficiency of the two approaches.
- When the iterative function runs with
n = 4, what is the value of the accumulatorresat the end of each iteration? - When the recursive function runs with
n = 4, what values does the parameterntake, in order? How is the result computed as the calls return, starting from the deepest call? - What are the time and space complexities of each approach? Explain using the execution steps from questions 1 and 2.
Reference answer
-
The loop variable
itakes the values1, 2, 3, 4in order. At the end of each iteration,resbecomes1, 3, 6, 10, respectively, so the iterative function returns 10. -
The parameter
nfollows the sequence4 → 3 → 2 → 1. The deepest call returns 1. The remaining calls then compute2 + 1 = 3,3 + 3 = 6, and4 + 6 = 10, in order. At the deepest point, all four function calls are still active. -
Both functions perform a number of iterations or calls proportional to \(n\), so both have time complexity \(O(n)\). Their space complexities differ: the iterative version uses only a constant number of variables, giving \(O(1)\). In the recursive version, earlier calls must wait for their results until the base case is reached. The call stack therefore holds up to \(n\) calls at once, giving space complexity \(O(n)\).
When analyzing space complexity, consider the space used by recursive calls as well as the variables in the code.
2. Time complexity of three code snippets¶
Each of the following three code snippets takes a positive integer \(n\) as input. Rank them from lowest to highest time complexity, and state each complexity.
def linear_loop(n: int) -> int:
"""Linear-time loop"""
res = 0
for i in range(n):
res += i
return res
def quadratic_loop(n: int) -> int:
"""Quadratic-time loop"""
res = 0
for i in range(n):
for j in range(i, n):
res += j
return res
def logarithmic_loop(n: int) -> int:
"""Logarithmic-time loop"""
while n > 1:
n //= 2
return n
/* Linear-time loop */
int linearLoop(int n) {
int res = 0;
for (int i = 0; i < n; ++i) {
res += i;
}
return res;
}
/* Quadratic-time loop */
int quadraticLoop(int n) {
int res = 0;
for (int i = 0; i < n; ++i) {
for (int j = i; j < n; ++j) {
res += j;
}
}
return res;
}
/* Logarithmic-time loop */
int logarithmicLoop(int n) {
while (n > 1) {
n /= 2;
}
return n;
}
/* Linear-time loop */
int linearLoop(int n) {
int res = 0;
for (int i = 0; i < n; i++) {
res += i;
}
return res;
}
/* Quadratic-time loop */
int quadraticLoop(int n) {
int res = 0;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
res += j;
}
}
return res;
}
/* Logarithmic-time loop */
int logarithmicLoop(int n) {
while (n > 1) {
n /= 2;
}
return n;
}
/* Linear-time loop */
int LinearLoop(int n) {
int res = 0;
for (int i = 0; i < n; i++) {
res += i;
}
return res;
}
/* Quadratic-time loop */
int QuadraticLoop(int n) {
int res = 0;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
res += j;
}
}
return res;
}
/* Logarithmic-time loop */
int LogarithmicLoop(int n) {
while (n > 1) {
n /= 2;
}
return n;
}
/* Linear-time loop */
func linearLoop(n int) int {
res := 0
for i := 0; i < n; i++ {
res += i
}
return res
}
/* Quadratic-time loop */
func quadraticLoop(n int) int {
res := 0
for i := 0; i < n; i++ {
for j := i; j < n; j++ {
res += j
}
}
return res
}
/* Logarithmic-time loop */
func logarithmicLoop(n int) int {
for n > 1 {
n /= 2
}
return n
}
/* Linear-time loop */
func linearLoop(n: Int) -> Int {
var res = 0
for i in 0 ..< n {
res += i
}
return res
}
/* Quadratic-time loop */
func quadraticLoop(n: Int) -> Int {
var res = 0
for i in 0 ..< n {
for j in i ..< n {
res += j
}
}
return res
}
/* Logarithmic-time loop */
func logarithmicLoop(n: Int) -> Int {
var n = n
while n > 1 {
n /= 2
}
return n
}
/* Linear-time loop */
function linearLoop(n) {
let res = 0;
for (let i = 0; i < n; i++) {
res += i;
}
return res;
}
/* Quadratic-time loop */
function quadraticLoop(n) {
let res = 0;
for (let i = 0; i < n; i++) {
for (let j = i; j < n; j++) {
res += j;
}
}
return res;
}
/* Logarithmic-time loop */
function logarithmicLoop(n) {
while (n > 1) {
n = Math.floor(n / 2);
}
return n;
}
/* Linear-time loop */
function linearLoop(n: number): number {
let res = 0;
for (let i = 0; i < n; i++) {
res += i;
}
return res;
}
/* Quadratic-time loop */
function quadraticLoop(n: number): number {
let res = 0;
for (let i = 0; i < n; i++) {
for (let j = i; j < n; j++) {
res += j;
}
}
return res;
}
/* Logarithmic-time loop */
function logarithmicLoop(n: number): number {
while (n > 1) {
n = Math.floor(n / 2);
}
return n;
}
/* Linear-time loop */
int linearLoop(int n) {
int res = 0;
for (int i = 0; i < n; i++) {
res += i;
}
return res;
}
/* Quadratic-time loop */
int quadraticLoop(int n) {
int res = 0;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
res += j;
}
}
return res;
}
/* Logarithmic-time loop */
int logarithmicLoop(int n) {
while (n > 1) {
n ~/= 2;
}
return n;
}
/* Linear-time loop */
fn linear_loop(n: i32) -> i32 {
let mut res = 0;
for i in 0..n {
res += i;
}
res
}
/* Quadratic-time loop */
fn quadratic_loop(n: i32) -> i32 {
let mut res = 0;
for i in 0..n {
for j in i..n {
res += j;
}
}
res
}
/* Logarithmic-time loop */
fn logarithmic_loop(mut n: i32) -> i32 {
while n > 1 {
n /= 2;
}
n
}
/* Linear-time loop */
int linearLoop(int n) {
int res = 0;
for (int i = 0; i < n; i++) {
res += i;
}
return res;
}
/* Quadratic-time loop */
int quadraticLoop(int n) {
int res = 0;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
res += j;
}
}
return res;
}
/* Logarithmic-time loop */
int logarithmicLoop(int n) {
while (n > 1) {
n /= 2;
}
return n;
}
/* Linear-time loop */
fun linearLoop(n: Int): Int {
var res = 0
for (i in 0 until n) {
res += i
}
return res
}
/* Quadratic-time loop */
fun quadraticLoop(n: Int): Int {
var res = 0
for (i in 0 until n) {
for (j in i until n) {
res += j
}
}
return res
}
/* Logarithmic-time loop */
fun logarithmicLoop(n: Int): Int {
var value = n
while (value > 1) {
value /= 2
}
return value
}
### Linear-time loop ###
def linear_loop(n)
res = 0
for i in 0...n
res += i
end
res
end
### Quadratic-time loop ###
def quadratic_loop(n)
res = 0
for i in 0...n
for j in i...n
res += j
end
end
res
end
### Logarithmic-time loop ###
def logarithmic_loop(n)
n /= 2 while n > 1
n
end
Reference answer
From lowest to highest: snippet 3, \(O(\log n)\); snippet 1, \(O(n)\); snippet 2, \(O(n^2)\). Snippet 3 halves \(n\) at each iteration, so it runs approximately \(\log_2 n\) times. Snippet 1 runs its loop exactly \(n\) times. In snippet 2, the inner loop runs \(n,n-1,\dots,1\) times in successive iterations, for a total of \(n(n+1)/2\), giving quadratic time complexity.
3. Which reversal method uses less space?¶
There are two ways to reverse all the elements in an array nums:
- Create an array
resof the same length, copy the elements into it in reverse order, and return it. -
Move two indices,
iandj, inward from the beginning and end, swappingnums[i]withnums[j]in pairs.What is the space complexity of each approach? Which operation is in-place?
Reference answer
-
An auxiliary array as long as the input is needed, giving space complexity \(O(n)\).
-
Only two index variables are used, giving space complexity \(O(1)\). This is an in-place operation.
Keep in mind that in-place reversal modifies the input array. Prefer it only when modifying the input is allowed. If the original array must be preserved, the copying cost of approach 1 is unavoidable.
2.6.2 Programming exercises¶
1. Fibonacci number¶
The Fibonacci sequence satisfies \(F(0)=0\), \(F(1)=1\), and, for \(n\ge2\), \(F(n)=F(n-1)+F(n-2)\).
Given a nonnegative integer n, use a loop to compute and return \(F(n)\) without recursion.
Hints
- Handle n equal to 0 or 1 separately first.
- Computing the next term requires only the previous two terms; there is no need to store the entire sequence.
- When updating the two variables, take care not to overwrite an old value before you have finished using it.