Concept
Big O Notation
big O, read as the letter O, not the numeral zero
Also Known As Landau Notation
Notation
Big O notation is a mathematical notation used to describe the limiting behavior of a function as its argument grows toward a particular value or infinity. In computer science it classifies algorithms by how their running time or space requirements grow as input size grows, providing an upper bound on that growth. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/
Facts
Origin YearProposed by Paul Bachmann in 1894 in a number theory context and extended by Edmund Landau in 1909; its use to classify algorithm running time came later. Core PrincipleExpresses that a function's growth is bounded above by another, usually simpler, function times a constant for sufficiently large inputs, letting algorithms be compared by growth rate rather than exact operation counts. 1 FAQs
Who created Big O notation and why is it sometimes called Landau notation?
Bachmann proposed it in 1894 and Landau extended it in 1909.
Paul Bachmann proposed the notation in 1894, and Edmund Landau extended it in 1909. Big O belongs to a family of notations invented by these two German mathematicians and expanded by others, which is why it is also known as Landau notation. Computer science later borrowed it to classify algorithms by how their running time or space requirements grow with the input size.
Connections
In Field
Source Wikipedia: Big O notation
Sources
1. Wikipedia: Big O notation
WikipediaIntroductory section, before Formal definition
Bachmann proposed the notation in 1894 and Landau extended it in 1909.
- Formal definition section
- Introductory section, Bachmann and Landau
Lead paragraph
Big O notation is a mathematical notation that describes the approximate size of a function on a domain.
Introduction section, Bachmann and Landau
Big O is a member of a family of notations invented by the German mathematicians Paul Bachmann and Edmund Landau and expanded by others, collectively called Bachmann-Landau notation.
Introduction
In computer science, big O notation is used to classify algorithms by how their run time or space requirements grow with the input.
- In Field: Algorithms and Complexity Theory
In Group: Mathematical and Formal Notations, Lead
Big O notation is a mathematical notation that describes the approximate size of a function on a domain.
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.