Big-O ले अल्गोरिदमको रनिङ टाइम वा मेमोरी इनपुट साइज n बढ्दै जाँदा कसरी बढ्छ भनी वर्णन गर्छ। यसले worst-case asymptotic behavior को कैद गर्छ, constants र lower-order terms लाई बेवास्ता गर्दै।
हामी growth rate को बारेमा सोच्छौँ, exact step counts को बारेमा होइन। O(2n + 5) साधारणतया O(n) हो किनभने n ठूलो हुँदा जाँदा, constants र साना terms महत्वपूर्ण हुँदैनन्।
| Big-O | नाम | उदाहरण |
|---|
| O(1) | constant | array index lookup |
| O(log n) | logarithmic | binary search |
| O(n) | linear | list स्क्यान गरिरहनु |
| O(n log n) | linearithmic | merge sort |
| O(n²) | quadratic | nested loops |
| O(2ⁿ) | exponential | naive subsets |
def has_duplicate(nums):
for i in range(len(nums)): # outer loop: n
for j in range(i + 1, len(nums)): # inner loop: n
if nums[i] == nums[j]:
return True
return False
# nested loops -> O(n^2) time, O(1) space
Big-O ले constants लाई लुकाउँछ: एक ठूलो constant भएको O(n) अल्गोरिदम साना inputs मा O(n log n) को विरुद्ध हार्न सक्छ। साथै space complexity ट्र्याक गर्नुस्, केवल time मात्र होइन।
Big-O ले तपाइँलाई अल्गोरिदमहरु तुलना गर्न दिन्छ तिनीहरु चलाउनु वा हार्डवेयरको बारेमा चिन्ता गरी नबिना।
यसले भविष्यद्वाणी गर्छ कि कुन समाधान inputs सयको देखि लखलाखमा बृद्धि हुँदा बच्छन् — feature जो scale गर्छ र अर्को जो timeout हुन्छ बीचको भेद।
यो vocabulary हो जुन हरेक इन्जिनियर performance को बारेमा तर्क गर्न प्रयोग गर्छ।