O-speedup

From Wikipedia, the free encyclopedia

Informally, an O-optimal algorithm is one that is optimal in Big O notation notation. More formally, an algorithm A accepting a language L is O-optimal if for any other A' accepting L, there exists a constant c such that for all inputs x: $time_A(x)\leq c(|x|+time_{M'}(x))$ . A language with no O-optimal A is said to have O-speedup.