تعريف رسمي نشانه گذاري O بزرگ
برنامه اي را در نظر بگيريد كه به صورت زير پياده سازي شده است:

for(i = 0; i < n; i++) {
for(j = 0; j < n; j++) {
Simple statement
}
}
for(k = 0; k < n; k++) {
Simple statement1
…
Simple statement5
}
Simple statement6
…
Simple statement30
فرض مي كنيم هر"Simple statement" يك واحد زماني را مصرف مي كند. حلقه داخلي، دستور Simple statement را n به توان 2
بار اجرا مي كند، سپس 5 دستور Simple statement

درحلقه اي با انديس kبه تعداد nبار اجرا مي شوند.سرانجام، 25دستور Simple statement اجرا مي گردند. بنابراين، داريم:


T(n)+n2+5n+25

اين عبارت، ارتباط بين زمان پردازش و n را نشان مي دهد. همان طور كه مشاهده مي كنيد، T(n) زمان پردازش را برحسب n بيان مي كند. اكنون رابطه زير را ببينيد:

T(n) = O(f(n))


اين رابطه به معناي اين است كه دو ثابت

n0و
c بزرگ تر از صفر، و تابع f(n) وجود دارند،
به طوري كه براي تمام n>n0
خواهيم داشت cf(n)<=T(n)
.به عبارت ديگر، وقتي n به

اندازه كافي بزرگ مي شود (بزرگ تر از n0
)، ثابتي مثل c وجود دارد كه براي آن، زمان


پردازش همواره كمتر يا مساوي cf(n) است.