Big-O यह बताता है कि किसी algorithm का चलने का समय या memory, input के आकार n के बढ़ने के साथ कैसे बढ़ता है। यह worst-case asymptotic व्यवहार को दर्शाता है, और constants तथा lower-order terms को नज़रअंदाज़ कर देता है।
हम growth rate की परवाह करते हैं, न कि exact step count की। 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 को scan करना |
| 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) algorithm छोटे inputs पर O(n log n) से हार सकता है। साथ ही केवल time ही नहीं, space complexity को भी ध्यान में रखें।
Big-O आपको algorithms को बिना चलाए या hardware की चिंता किए तुलना करने देता है।
यह बताता है कि जब inputs सैकड़ों से बढ़कर लाखों हो जाते हैं, तो कौन-से solutions टिक पाते हैं — यही फ़र्क है एक ऐसे feature और दूसरे के बीच जो time out हो जाता है।
यह वह शब्दावली है जिसका उपयोग हर engineer performance के बारे में सोचने के लिए करता है।