Bresenham Algorithm (Rasterization Rasterization)

Time Complexity

$O(n)$

Space Complexity

$O({1})$ Words

(Derived: for each iteration (i.e. each step along the line), only need to store a constant number of variables that are then overwritten in the next iteration.)

Approximate?

Approximate

Approximation Factor: n/a

Randomized?

No, deterministic

Model of Computation

Word RAM

Year

1962

Reference

Hearn, Baker (1997) pg. 88