Complexity Exercises: Practice Big-O Analysis
Time to practice analyzing complexity. For each snippet, work out its time and space complexity in Big-O before checking the answer — say it out loud, then justify it by counting loops or writing the recurrence. Every View answer link jumps to a full explanation on the complexity solutions page.
How to practice: Re-read analyzing loops and analyzing recursion first. Then for each question, name the dominant term and explain why in one sentence. The reasoning matters more than the letter.
Warm-ups
Q1. Single loop. A function loops for i in 0..n-1 and does a constant amount of work each iteration. What is its time and space complexity?
Q2. Two sequential loops. A function runs one loop of n iterations, then a separate loop of m iterations (different input sizes). What is the time complexity? Is it ever correct to call this O(n)?
Q3. The doubling loop. A loop starts at i = 1 and does i *= 2 until i >= n. How many times does it run, in Big-O?
Core
Q4. The triangular nested loop. The outer loop runs i from 0 to n-1; the inner loop runs j from i+1 to n-1. What is the time complexity, and why isn’t it O(n²/2)?
Q5. Misleading nesting. An outer loop runs n times; inside it, a while loop halves a copy of n down to 1 each outer iteration. What is the overall time complexity?
Q6. Recursive cost. A function makes two recursive calls on input of size n-1 and does O(1) work per call. Write the recurrence and give the Big-O.
Challenge
Q7. Choose the better complexity. You must find whether any value appears twice in an array. Approach A compares every pair of elements. Approach B inserts elements into a hash set and checks membership. Give each approach’s time and space complexity, and say which you’d choose and when.
Done? Check every answer on the complexity answer sheet — including the ones you got right, since the explanations show the fastest way to reason. Then move on to arrays.