(صرفا جهت اطلاع)
تعریف ریاضی تابع O که در کتاب طراحی الگوریتم با رویکرد خلاقانه نوشته ی یودی منبر آمده است:
برای ارزیابی زمان اجرای یک الگوریتم، از عوامل ثابت چشم پوشی میکنیم. برای بهتر انجام دادن این کار به نماد گذاری ویژه ای احتیاج داریم. میگوییم تابع ( g( n از ( ( O ( f (n است اگر ثابت های c و N وجود داشته باشند به گونه ای که برای n>=N داشته باشیم:
g(n) <= c.f(n)
به عبارت دیگر به ازای n های به اندازه ی کافی بزرگ، تابع( g( n از چند برابر تابع( f( n بیشتر نیست. (در این جا "چند" ضریبی ثابت است)
تبصره: ممکن است برای n های کوچک، ( g( n از ( c.f( n خیلی کوچکتر باشد ولی نماد O، آن را تنها از بالا محدود میکند.
مثلا 5n^2 + 15 از ( O( n^2 است.