Skip to main content

Welcome to Programming and Data Structures

Andrew Scholer

Section 25.8 Analyzing a Longer Chunk

Now let us consider a longer chunk of code:
🔗
int sum = 0;
for (int i = 0; i < n; i++) {
  for (int j = 0; j < n; j *= 2) {
    sum = sum + i + j;
  }
}

if (n % 2 == 0) {
  sum = sum + 1;
} else {
  sum = sum + 2;
}

for (int k = 1; k <= n/2; k++) {
  int x = 1 + k;
  sum = sum + x;
}
return sum;
To analyze this code, we can:
  1. Call any sequence of lines that do not involve loops or function calls \(O(1)\text{.}\)
    🔗
  2. Calculate the number of iterations of each loop.
    🔗
  3. When loops are nested, multiply the number of iterations of each loop to get the total number of iterations.
    🔗
  4. Add whatever remains and only keep the dominant term.
    🔗
🔗

Exploration 25.8.1.

We will analyze the given code to determine its Big-O complexity.
🔗

(a) Start.

First, we replace non-loops with \(O(1)\text{.}\)
🔗
int sum = 0;
for (int i = 0; i < n; i++) {
  for (int j = 0; j < n; j *= 2) {
    sum = sum + i + j;
  }
}

if (n % 2 == 0) {
  sum = sum + 1;
} else {
  sum = sum + 2;
}

for (int k = 1; k <= n/2; k++) {
  int x = 1 + k;
  sum = sum + x;
}
return sum;
🔗

(b) Identify loop lengths.

That results in the following.
🔗
// O(1)
for (int i = 0; i < n; i++) {
  for (int j = 0; j < n; j *= 2) {
    // O(1)
  }
}

// O(1)

for (int k = 1; k <= n/2; k++) {
  // O(1)
}
// O(1)
Next, we identify the lengths of each loop.
🔗
🔗

(c) Identify loop lengths.

Here, each loop is labeled with the number of repetitions. Note that:
  • the i loop counts from 0 to n by 1s, so it has a length of \(O(n)\)
    🔗
  • the j loop, which multiplies by 2 at each step, has a length of \(O(\log n)\)
    🔗
  • the k loop, which counts from 1 up to \(n/2\) by 1s, has a length of \(O(n)\)
    🔗
🔗
// O(1)
loop O(n) times {  (i loop)
  loop O(log n) times {  (j loop)
    // O(1)
  }
}

// O(1)

loop O(n) times { (k loop)
  // O(1)
}
// O(1)
Next, we multiply loops by what is inside them.
🔗
🔗

(d) Multiply Loops by Contents.

We start with the inner loop (j loop). It runs \(O(\log n)\) times, and its contents are \(O(1)\text{,}\) so the total is \(O(\log n) \cdot O(1) = O(\log n)\text{.}\)
🔗
// O(1)
loop O(n) times { (i loop)
  // O(log n)  (j loop)
}
// O(1)
loop O(n) times { (k loop)
  // O(1)
}
// O(1)
Now we have no nested loops, so we can multiply the remaining loops by their contents.
🔗
🔗

(e) Multiply Loops by Contents.

The i loop runs \(O(n)\) times, and its contents are \(O(\log n)\text{,}\) so the total is \(O(n) \cdot O(\log n) = O(n \log n)\text{.}\)
🔗
// O(1)
// O(n log n) (i loop with j inside)
// O(1)
loop O(n) times { (k loop)
  // O(1)
}
// O(1)
Next the k loop.
🔗
🔗

(f) Multiply Loops by Contents.

The k loop runs \(O(n)\) times, and its contents are \(O(1)\text{,}\) so the total is \(O(n) \cdot O(1) = O(n)\text{.}\)
🔗
// O(1)
// O(n log n) (i loop with j inside)
// O(1)
// O(n) (k loop)
// O(1)
We have
\begin{equation*} O(1) + O(n \log n) + O(1) + O(n) + O(1)\text{.} \end{equation*}
That is
\begin{equation*} O(n \log n) + O(n) + 3 \cdot O(1) \end{equation*}
which is just
\begin{equation*} O(n \log n) + O(n) + O(1)\text{.} \end{equation*}
🔗
Of those, the dominant term is \(O(n \log n)\text{.}\) So the Big-O complexity is \(O(n \log n)\text{.}\)
🔗
Since all we care about is the dominant term, we didn’t even have to add up the various terms. We could have simply looked at the four terms we ended up with and picked the largest one!
🔗
🔗
🔗

Checkpoint 25.8.1.

We want to analyze this program fragment:
🔗
int sum = 0;
for (int i = 0; i < n; i += 2) {
  for (int j = 0; j < i; j++) {
    sum = sum + i + j;
  }
}

int total = 0;
for (int i = 1; i <= n; i++) {
  int x = 1 + i;
  for (int j = 0; j < n; j *= 2) {
    total = total + i + j;
    total = total * 2;
  }
}
if (sum > total) {
  total = sum;
}
return sum;
Arrange the correct blocks from below so that the first step is on top, the next logical step is below that, etc... The last block will have the final Big-O complexity.
🔗
You will not use all the blocks.
🔗
🔗
You have attempted of activities on this page.
🔗
PrevTopNext