# Bresenham Algorithm (Rasterization Rasterization)

Jump to navigation
Jump to search

## 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.)

## Description

## Approximate?

Approximate

Approximation Factor: n/a

## Randomized?

No, deterministic

## Model of Computation

Word RAM

## Year

1962

## Reference

Hearn, Baker (1997) pg. 88