⏳ Time Complexity ⏳ and 🌌 Space Complexity 🌌

 Follow Me

✅ What is Time Complexity?

Time Complexity is the measure of how the execution time of an algorithm grows relative to the input size (n).

It tells us how fast an algorithm is.

🔹 Common Time Complexities:

Big-O Notation	Name	Description
O(1)	Constant Time	Time doesn't grow with input size
O(log n)	Logarithmic	Time grows slowly as input increases
O(n)	Linear	Time grows directly with input
O(n log n)	Linearithmic	Time grows faster than linear but less than quadratic
O(n²)	Quadratic	Time grows with the square of input size
O(2ⁿ)	Exponential	Time doubles with each addition to input size
O(n!)	Factorial	Time grows extremely fast (used in permutations etc.)

🧠 Example in Python (Time Complexity O(n)):

def find_max(arr): max_num = arr[0] for num in arr: if num > max_num: max_num = num return max_num

• Here, the function iterates once over the array → O(n) time.

✅ What is Space Complexity?

Space Complexity refers to the amount of memory used by an algorithm as a function of the input size.

It includes both temporary variables and recursive stack space.

🔹 Common Space Complexities:

Big-O Notation	Description
O(1)	Uses constant space
O(n)	Uses space proportional to input
O(n²)	Uses space for matrices or nested structures

🧠 Example in Python (Space Complexity O(n)):

def duplicate_list(arr): new_list = [] for item in arr: new_list.append(item) return new_list

• Here, the function creates a new list of the same size → O(n) space.

🔄 Key Differences: Time vs Space Complexity

Feature	Time Complexity	Space Complexity
Definition	Measures execution time growth	Measures memory usage growth
Concerned with	CPU usage	Memory/RAM usage
Example Metric	Loops, recursion, function calls	Variables, data structures, call stack
Goal	Optimize speed	Optimize memory usage
Common Trade-off	More speed can cost more memory (vice versa)	Use memoization: faster but more space

📌 How to Analyze Time and Space Complexity in Python?

🔹 Step-by-Step:

1. Count the Loops – Each nested loop adds a layer to time complexity.

2. Check Recursive Depth – For recursion, count calls and stack usage.

3. Track Memory Allocation – New lists, sets, dicts use memory.

4. Ignore Constants – Big-O ignores low-level constants.

🧪 Examples with Both Time and Space Complexity

✅ Example 1: Linear Search

def linear_search(arr, target): for i in range(len(arr)): if arr[i] == target: return i return -1

• Time Complexity: O(n) → worst case checks every element.

• Space Complexity: O(1) → no extra space.

✅ Example 2: Merge Sort (Recursive)

def merge_sort(arr): if len(arr) <= 1: return arr mid = len(arr) // 2 left = merge_sort(arr[:mid]) right = merge_sort(arr[mid:]) return merge(left, right) def merge(left, right): result = [] while left and right: result.append(left.pop(0) if left[0] < right[0] else right.pop(0)) result.extend(left + right) return result

• Time Complexity: O(n log n)

• Space Complexity: O(n) → due to the result and recursion stack.

✅ Example 3: Fibonacci (Recursive vs Dynamic)

❌ Naive Recursion:

def fib(n): if n <= 1: return n return fib(n-1) + fib(n-2)

• Time: O(2ⁿ), Space: O(n)

✅ Memoization (Dynamic Programming):

def fib(n, memo={}): if n in memo: return memo[n] if n <= 1: return n memo[n] = fib(n-1, memo) + fib(n-2, memo) return memo[n]

• Time: O(n), Space: O(n)

🧾 Summary Table

Algorithm	Time Complexity	Space Complexity
Linear Search	O(n)	O(1)
Binary Search	O(log n)	O(1)
Bubble Sort	O(n²)	O(1)
Merge Sort	O(n log n)	O(n)
Quick Sort	O(n log n) avg	O(log n)
Fibonacci (Rec)	O(2ⁿ)	O(n)
Fibonacci (Memo)	O(n)	O(n)

💡 Bonus Tip: Use Python's time and sys modules to measure

import time import sys start = time.time() # your_function() print("Time:", time.time() - start) print("Memory:", sys.getsizeof(your_object))