2015/11/16 by Holger Petersen, Petersen, Holger
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #Computational Complexity (cs.CC) #DNA and Biological Computing #FOS: Computer and information sciences #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1511.05210
openalex publication_date 2015/11/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A lower time bound Ω(min(ν(x), n-ν(x)) for counting the number of ones in a binary input word x of length n is presented, where ν(x) is the number of ones. The operations available are increment, decrement, bit-wise logical operations, and assignment. The only constant available is zero. An almost matching upper bound is also obtained.