bobluppes / bobluppes/graaf

Document time/space complexity consistently across all algorithm docs

Aperta Adatta ai principianti
#327 0 commenti 0 reazioni 0 assegnatari Vedi su GitHub
Lingua principale
C++
Stelle
413
Fork
67
Merge medio
7h 24m
PR unite (30g)
53

Descrizione

## Summary

Time/space complexity is documented for some algorithms but not others, making the algorithm documentation an unreliable reference for choosing between algorithms at scale.

## Current state

Spot-checking [docs/docs/algorithms/](../tree/main/docs/docs/algorithms):

- [`shortest-path/dijkstra.md`](../blob/main/docs/docs/algorithms/shortest-path/dijkstra.md) explicitly states `O(|E|log|V|)`.
- [`clique-detection/bron_kerbosch.md`](../blob/main/docs/docs/algorithms/clique-detection/bron_kerbosch.md), [`coloring/welsh-powell.md`](../blob/main/docs/docs/algorithms/coloring/welsh-powell.md), [`minimum-spanning-tree/kruskal.md`](../blob/main/docs/docs/algorithms/minimum-spanning-tree/kruskal.md), [`strongly-connected-components/tarjan.md`](../blob/main/docs/docs/algorithms/strongly-connected-components/tarjan.md), and [`traversal/breadth-first-search.md`](../blob/main/docs/docs/algorithms/traversal/breadth-first-search.md) describe *what* the algorithm does and its syntax, but state no time or space complexity at all.

This inconsistency runs across essentially all algorithm categories (traversal, shortest-path, MST, SCC, coloring, clique-detection), not just one or two pages.

## Why this matters

Complexity is one of the first things engineers need in order to choose between algorithms (e.g. Bellman-Ford vs. Dijkstra vs. A*) and to reason about whether a given algorithm will scale to a target graph size before integrating it. Without it stated consistently, users either have to read the implementation themselves or guess, which undermines confidence in the library for anything beyond casual/prototype use.

## Suggested resolution

- Add a standard "Complexity" subsection (time and space, worst-case, in terms of `|V|`/`|E|`) to every algorithm doc page, matching the level of detail already present on the Dijkstra page.
- Consider enforcing this via the existing `.github/ISSUE_TEMPLATE/algorithm-documentation-template.md` / `new-algorithm-template.md` templates, so new algorithm docs can't be added without it.

## Acceptance criteria

- [ ] Every page under `docs/docs/algorithms/` states time and space complexity.
- [ ] The algorithm-documentation issue template requires a complexity section for future additions.

Guida per i contributori

Apri la guida per i contributori

Direzione di ricerca

Review the existing algorithm documentation pages in `docs/docs/algorithms/`, starting with the provided examples like `dijkstra.md`. Identify the missing complexity sections. For each algorithm, research or infer its standard time/space complexity (e.g., O(|V| + |E|) for BFS). Add a 'Complexity' subsection to each page, following the format in `dijkstra.md`. Also, update the template files `.github/ISSUE_TEMPLATE/algorithm-documentation-template.md` and `new-algorithm-template.md` to include a required complexity section.

Scritto dal modello di indicizzazione a partire dal testo della issue.

Valutazione

Stack tecnologico
cpp, markdown
Ambito
documentation
Tipo di issue
Documentazione
Difficoltà
2/5
Tempo stimato
1-3 ore
Stato di attività
Attiva
Chiarezza
Specificata chiaramente
Idoneità per principianti
75/100

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.