Scribd
Upload
37 views2 pages

Time and Space Complexity in Python

The document discusses time and space complexity in algorithms, highlighting their importance in evaluating efficiency. It provides a detailed overview of common time complexities using Big O notation and outlines the complexities associated with various data structures and algorithms. Additionally, it includes Python code examples to illustrate different complexities.

Uploaded by

Prashant Patel
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
37 views2 pages

Time and Space Complexity in Python

The document discusses time and space complexity in algorithms, highlighting their importance in evaluating efficiency. It provides a detailed overview of common time complexities using Big O notation and outlines the complexities associated with various data structures and algorithms. Additionally, it includes Python code examples to illustrate different complexities.

Uploaded by

Prashant Patel
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Time and Space Complexity in Data Structures and

Algorithms (Python)
Complexity Analysis helps us understand how efficient an algorithm is in terms of time and
memory. There are two main types: Time Complexity: Measures how execution time grows with
input size (n). Space Complexity: Measures how much memory an algorithm uses with input size.

Common Time Complexities


Big O Name Description Example
O(1) Constant Execution time doesn’t depend on input size Access element in list
O(log n) Logarithmic Time grows slowly with n Binary Search
O(n) Linear Time grows directly with n Traversing list
O(n log n) Linearithmic Efficient sorting algorithms Merge Sort
O(n²) Quadratic Nested loops Bubble Sort
O(2■) Exponential Doubles with each input Recursive Fibonacci
O(n!) Factorial Extremely slow Travelling Salesman Problem

Time and Space Complexity of Common Data Structures


Data Structure Operation Average Time Worst Time Space
List Access O(1) O(1) O(n)
List Insert O(1) O(n) O(n)
Set Search O(1) O(n) O(n)
Dict Insert/Search/Delete O(1) O(n) O(n)
Stack Push/Pop O(1) O(1) O(n)
Queue Enqueue/Dequeue O(1) O(1) O(n)
Linked List Search O(n) O(n) O(n)
BST Search/Insert/Delete O(log n) O(n) O(n)
Heap Insert/Delete O(log n) O(log n) O(n)

Algorithm Complexities
Algorithm Best Average Worst Space
Linear Search O(1) O(n) O(n) O(1)
Binary Search O(1) O(log n) O(log n) O(1)
Bubble Sort O(n) O(n²) O(n²) O(1)
Merge Sort O(n log n) O(n log n) O(n log n) O(n)
Quick Sort O(n log n) O(n log n) O(n²) O(log n)
Heap Sort O(n log n) O(n log n) O(n log n) O(1)

Python Examples
O(1) Example:
def get_first(arr):
return arr[0]

O(n) Example:
def print_all(arr):
for x in arr:
print(x)

O(log n) Example (Binary Search):


def binary_search(arr, target):
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target: return mid
elif arr[mid] < target: low = mid + 1
else: high = mid - 1
return -1

Summary:
Use Big O notation to describe performance. Strive for lower time (e.g., O(1), O(log n)) and
reasonable space (O(n)). Data structures affect both time and space efficiency.

You might also like