Linear growth, in the sense of asymptotic notation, means that an eventually positive real-valued
function 
satisfies 
as 
tends to infinity,
using big-theta notation. Equivalently, there
exist positive constants 
, 
, and 
such that
 |
for all 
(Cormen et al. 2001, p. 42). The same definition applies to a sequence 
as 
.
Every linear function 
with 
has linear growth. The stronger condition
 |
also implies linear growth, but the converse fails. For example, 
satisfies 
for 
, while its ratio to 
has no limit as 
.
Superlinear growth instead requires 
. A linear time
bound 
supplies only an upper bound and does not by itself
imply linear growth in this two-sided sense.
