Skip to content
Ameen Abozaid
Englishالعربية
BEG-039

Algorithms and complexity

  • 6 Lessons
  • 68 min of reading
  • 3 h practice (estimate)
Start module
On this page 8 topics

Overview

Topics

  • Big O
  • time vs space complexity
  • best/average/worst cases

Learn first

68 min of reading · 3 h of practice (estimate)

Learning outcomes

  1. Express the time complexity of simple code in Big O (O(1), O(log n), O(n), O(n log n), O(n²)).
  2. Distinguish time and space complexity and best, average, and worst cases.
  3. Compare two solutions to the same problem by complexity and choose one.

Lessons

  1. 01Why we measure growth, not seconds12 min read
  2. 02Big O notation11 min read
  3. 03Analyzing loops and nested loops12 min read
  4. 04Space complexity10 min read
  5. 05Best, average, worst11 min read
  6. 06Demo: turning an O(n²) solution into O(n)12 min read

Lab and exercises

Lab

BEG-039-LAB1 · Analyze and improve

Outcomes: 1–3 · Time: ~3 h

  1. State the time complexity of eight provided snippets (constant, single loop, nested loop, halving loop, hidden contains, and so on) and write a one-line reason for each.
  2. Rewrite two O(n²) solutions (for example duplicate detection and "find a pair with a given sum") as O(n) using a Set or Map.
  3. Time old and new versions on three input sizes and record the table.

Acceptance: correct analysis; measured speed-up.

Exercises (assessment: complexity quiz of 10 snippets; six exercises)

IDOutcomeTask
BEG-039-EX011Give the Big O: a[5]; a single loop over n; two nested loops over n; a loop with i *= 2; a sort with Collections.sort.
BEG-039-EX021Simplify to Big O: 3n + 10, n² + n, 100, n log n + n.
BEG-039-EX032State the time and space complexity of reversing an array into a new array, and of reversing it in place.
BEG-039-EX042For linear search in an array, describe the best, average, and worst case and the input that causes each.
BEG-039-EX053Two solutions check whether a list has two equal items: nested loops, or a HashSet. Compare by time and space and choose one; say when you would choose the other.
BEG-039-EX061A loop over n calls list.remove(0) on an ArrayList each time. What is the total complexity and why?
Show solutions
  • EX01 O(1); O(n); O(n²); O(log n); O(n log n).
  • EX02 O(n); O(n²); O(1); O(n log n).
  • EX03 New array: O(n) time, O(n) space. In place with two indexes: O(n) time, O(1) space.
  • EX04 Best: target is first, 1 step. Worst: target last or missing, n steps. Average: about n/2 steps, still O(n).
  • EX05 Nested loops: O(n²) time, O(1) space. HashSet: O(n) time, O(n) space. Choose the HashSet for large inputs; nested loops only if memory is very tight or n is tiny.
  • EX06 O(n²): remove(0) shifts all remaining items (O(n)), done n times.
  • Outcome 3 is also covered by the lab (rewrite and measure) and the quiz.

Quiz

Outcomes: O1 express Big O · O2 time vs space, best/average/worst · O3 compare solutions.

A self-check for you: nothing is graded, saved or sent anywhere. Choose an answer, then check it. You can try again as often as you like.

  1. 1int x = arr[10]; is:O1
  2. 2A single for loop from 0 to n doing constant work is:O1
  3. 3Two nested loops, each over n:O1
  4. 4for (int i = 1; i < n; i *= 2) is:O1
  5. 53n² + 5n + 9 simplifies to:O1
  6. 6A loop over a List of n items calling list.contains(x) inside is:O1
  7. 7Extra memory that grows with the input is called:O2
  8. 8Linear search's best case is:O2
  9. 9Why quote the worst case?O2
  10. 10Finding duplicates in a big list: which is faster for large n?O3

Practical part

Six exercises BEG-039-EX01 to EX06 plus the lab. The assessment is the 10-snippet complexity quiz (the ten questions above plus the lab snippets): pass at 8 of 10, and a lab with correct analysis and a measured speed-up.

Common mistakes

Counting only the outer loop; ignoring hidden loops (list.contains).

Assessment

Complexity quiz (10 snippets).

Career relevance

Capacity planning (SRC-004) and interview questions at every level.

Type to search levels, phases, modules and lessons.