एक Algorithm की time complexity, अल्गोरिथम के द्वारा अपनी process को पूरा करने में लगने वाले कुल समय की मात्रा है। ज्यादातर अल्गोरिथम की टाइम कॉम्प्लेक्सिटी को Big O notation का उपयोग करके व्यक्त किया जाता है। यह एक asymptotic notation है। इसको व्यक्त करने के सभी notations निम्नलिखित है।
- Big O – O(n),
- Bi.g Theta – Θ(n)
- Big Omega – Ω(n)
execution को समाप्त करने के लिए किसी भी एल्गोरिथम द्वारा perform किये गए steps की संख्या की गिनती (counting) के द्वारा time complexity को estimate किया जाता है।
Space Complexity
एक Algorithm की space complexity अल्गोरिथम के द्वारा ली गयी space की मात्रा है। स्पेस कॉम्प्लेक्सिटी के अंदर auxiliary space तथा input के द्वारा use लिया गया space दोनों आते हैं। auxiliary space जो है वह algorithm के द्वारा execution के दौरान प्रयोग किया गया temporary space या extra space होता है।
एक अल्गोरिथम की space complexity को Big O (O(n)) notation के द्वारा व्यक्त किया जाता है। बहुत सारीं algorithms के पास inputs होते हैं जो size में भिन्न भिन्न होते हैं। ऐसी स्थिति में space complexity जो है वह input के size पर निर्भर रहती है।