Time complexity: loops and the master theorem, quick guide

Most time complexity questions in exams reduce to two skills: counting how many times a loop body runs, and solving a recurrence. Loops A loop for (i = 1; i <= n; i++) runs n times, so O(n). A loop w