1. Complexity

Analyzing code

0 of 5 activities0%

Reading 1

Recipes for analysis

Open

Add costs of sequential blocks. Multiply costs of nested loops when the inner depends on the outer bound.

Space complexity counts extra memory besides the input. An O(n) array uses O(n) space; a few variables use O(1).

Logarithmic often appears when you repeatedly halve the search space.

// O(n log n) sketch: n times, and each does log n work
for (int i = 0; i < n; i++) {
  int x = n;
  while (x > 1) x /= 2; // ~log n
}

Check 2

Open

A loop that starts at n and does x = x/2 until x==1 is typically

Fill in 3

Open

Try it 4

Open

Outer n, inner n → about n*n iterations.

main.cpp

Loading editor…

Program input (stdin)

Output will appear here.

Assignment 5

Open

Read n. Print n*n (the iteration count of an n by n nested loop).

main.cpp

Loading editor…