Linear

• function: $\Theta(n)$.
• recurrence: T(1) = 1, T(n) = 1 + T(n-1)
• context: Singly-nested loops, visit everything once.
• examples: Naive multiplication, depth-first search.
• variations: T(n) = 1 + 2 T(n/2), T(n) = n + T(n/2), T(n) = T(n/5)+T(7n/10 + 6) + n.