Home›String Algorithm›Time Complexity›Linear Time -- O(n)Browse ByLinear Time -- O(n)This dimension groups algorithms by their time complexity, how the time an algorithm takes grows with the size of its input. Wikipedia notes that an algorithm "terminates after a finite number of steps," and how many steps it needs is exactly what time complexity measures. Browsing by time complexity keeps algorithms of a similar efficiency grouped together.FactsLinear Time -- O(n)SourcesComments (0)Reader Challenges (0)FactsComparisonEra of EmergenceWell-attested1977 CE 1Linear Time -- O(n)Filter Results22 entriesCategoryAllData Compression Algorithms (6)Formal Languages and Automata Theory (1)Parsing Algorithms (2)Phonetic Matching Algorithms (1)String Matching and Compression Algorithms (1)String Searching Algorithms (6)Design TechniqueAllApproximation Algorithms (1)Divide and Conquer (1)Dynamic Programming (1)Heuristics (1)Invented ByAllAbraham Lempel (1)Alfred Aho (1)Craig Nevill-Manning (1)David Wheeler (1)Edsger W. Dijkstra (1)Edward Fredkin (1)Esko Ukkonen (1)Ian H. Witten (1)J Strother Moore (1)Jacob Ziv (1)Ken Thompson (1)Masaru Tomita (1)Robert S. Boyer (2)Terry Welch (1)Invented By CompanyAllMeta Platforms, Inc. (1)GroupAllData Compression Algorithms (6)Formal Languages and Automata Theory (1)Parsing Algorithms (2)Phonetic Matching Algorithms (1)String Matching and Compression Algorithms (1)String Searching Algorithms (6)Credited ToAllAbraham Lempel (1)Alfred Aho (1)Craig Nevill-Manning (1)David Wheeler (1)Edsger W. Dijkstra (1)Edward Fredkin (1)Esko Ukkonen (1)Ian H. Witten (1)J Strother Moore (1)Jacob Ziv (1)Ken Thompson (1)Masaru Tomita (1)Nigel Horspool (1)Robert S. Boyer (1)Terry Welch (1)ACM AreaAllAlgorithms and Complexity Theory (12)Theory of Computation (1)Show ResultsBrowseCompareSelect all 22Aho-Corasick AlgorithmLinear Time -- O(n)Arithmetic Coding AlgorithmLinear Time -- O(n)BLAST (Biotechnology)Linear Time -- O(n)Boyer-Moore AlgorithmLinear Time -- O(n)Boyer-Moore-Horspool AlgorithmLinear Time -- O(n)Brotli AlgorithmLinear Time -- O(n)Burrows-Wheeler Transform AlgorithmLinear Time -- O(n)Bzip2 AlgorithmLinear Time -- O(n)GLR ParserLinear Time -- O(n)LZMA AlgorithmLinear Time -- O(n)LZW AlgorithmLinear Time -- O(n)Manacher's AlgorithmLinear Time -- O(n)Run-Length EncodingLinear Time -- O(n)Sequitur algorithmLinear Time -- O(n)Shunting Yard AlgorithmLinear Time -- O(n)Soundex AlgorithmLinear Time -- O(n)Suffix Array Construction AlgorithmLinear Time -- O(n)Thompson's constructionLinear Time -- O(n)Trie AlgorithmLinear Time -- O(n)Ukkonen's AlgorithmLinear Time -- O(n)Z AlgorithmLinear Time -- O(n)Zstandard AlgorithmLinear Time -- O(n)Sources1. Wikipedia: Knuth-Morris-Pratt algorithmtier 2WikipediaKnuth-Morris-Pratt algorithm, History sectionQuote, Knuth-Morris-Pratt algorithm, History sectionThe three also published the algorithm jointly in 1977.View the SourceComments (0)No comments yet. Be the first to share a thought.Sign in to join the discussion.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.