لديك مصفوفة فيها $n$ عناصر. إذا قرأت كل عنصر مرة واحدة، فأنت تنجز $n$ عمليات أساسية. هذا هو مدخلنا لتحليل الزمن: نعدّ العمل عندما يكبر المدخل.

for (int i = 0; i < n; ++i)
    work();

يأخذ المؤشر القيم من صفر حتى $n-1$. عددها $n$، وتكلفة كل استدعاء ثابتة. مع تكاليف الشرط والزيادة يصبح الزمن من شكل $an+b$، لذا نصفه بأنه $\Theta(n)$.

ثلاث صيغ، لكل منها معنى

• $O(n)$: حدّ علوي. لا يتجاوز العمل مضاعفًا ثابتًا من $n$ بعد نقطة معينة.
• $\Omega(n)$: حدّ سفلي. لا يقل العمل عن مضاعف موجب ثابت من $n$ بعد نقطة معينة.
• $\Theta(n)$: حدّ محكم يجمع الحدّين.

مثلًا، $3n+7$ يقع بين $3n$ و$10n$ عندما $n\ge1$، ولذلك هو $\Theta(n)$. ويصحّ أيضًا أنه $O(n^2)$، لكنه حدّ فضفاض.

تذكّر: «أسوأ حالة» تختار المدخلات التي نحللها؛ وBig O تصف حدًا للدالة الناتجة. لا تخلط بينهما.

نستخدم نموذجًا تكون فيه المقارنة والعملية الأساسية على أعداد محدودة السعة بزمن ثابت.