Bresenham's line algorithm (Line Drawing Line Drawing)

Time Complexity

$O(n)$

Space Complexity

$O({1})$ words?

(Constant number of O(1)-word-sized variables (for determining which pixels to shade) is sufficient)

Approximate?

Exact

Randomized?

No, deterministic

Model of Computation

Word RAM?

Year

1965

Reference

https://web.archive.org/web/20080528040104/http://www.research.ibm.com/journal/sj/041/ibmsjIVRIC.pdf