{
  "id": "enwiki-001327938154",
  "slug": "output-sensitive-algorithm",
  "title": "Output-sensitive algorithm",
  "qid": "",
  "lead": "In computer science, an output-sensitive algorithm is an algorithm whose running time depends on the size of the output, instead of, or in addition to, the size of the input. For certain problems where the output size varies widely, for example from linear in the size of the input to quadratic in the size of the input, analyses that take the output size explicitly into account can produce better runtime bounds that differentiate algorithms that would otherwise have identical asymptotic complexity.",
  "body": "In computer science, an output-sensitive algorithm is an algorithm whose running time depends on the size of the output, instead of, or in addition to, the size of the input. For certain problems where the output size varies widely, for example from linear in the size of the input to quadratic in the size of the input, analyses that take the output size explicitly into account can produce better runtime bounds that differentiate algorithms that would otherwise have identical asymptotic complexity. def divide(number: int, divisor: int) -> tuple[int, int]: \"\"\"Division by subtraction.\"\"\" if divisor == 0: raise ZeroDivisionError if number = divisor: q += 1 r -= divisor return q, r Example output: >>> divide(10, 2) (5, 0) >>> divide(10, 3) (3, 1) This algorithm takes Θ(Q) time, and so can be fast in scenarios where the quotient Q is known to be small. In cases where Q is large however, it is outperformed by more complex algorithms such as long division. ==See also== Lazy evaluation",
  "categories": [
    "23118434",
    "23603337",
    "25257581",
    "29176158"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1327938154",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1765925133.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001327938154",
    "type": "webpage",
    "title": "Output-sensitive algorithm",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/output-sensitive-algorithm",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          18
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          18
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001327938154",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1327938154",
    "note": "Immutable snapshot enwiki-001327938154"
  }
}