Big-O complexities

Big-O complexities

https://wiki.python.org/moin/TimeComplexity

Big-O notation is used in computer science to describe the performance or complexity of an algorithm. It describes how the runtime or space requirement of a function grows as the input grows.

Algorithms usually fall into the following performance classes:

  • Constant-time → O(1)
  • Logarithmic → O(log N)
  • Linear → O(N)
  • Polynomial → O(n^2), O(n^3), O(n^x)
  • Exponential → O(2^n) (a^n=a×a×a×a...×a)
  • Factorial → O(n!) (n!=1×2×3×4...×n) factorial grows faster than exponential

Data type conversion

  • int to a float -> O(1)
  • int to a str and str to int -> O(n^2) → O(n)
  • str to a float -> O(n)
  • float to any type -> O(1)
  • list to set -> O(n)
  • list to tuple -> O(n)
  • string concat → O(n^2)

Sorting

sorted(list) → O(n log n)

bubble sort → O(n^2)

merge sort → O(n log n)

heap sort → O(n log n)

Lists

image

Deque

image

Dictionaries

image

Sets

image

deque (queue, stack)

image
  • Index access of deque is O(N). WHY? Unlike Python's standard list (which uses a single contiguous block of memory and supports true O(1) random access), collections.deque is implemented as a doubly-linked list of blocks (fixed-size memory chunks, typically 64 elements each)

heapq (priority queue, min heap by default)

Operation
Standard list
heapq
Access Minimum (heap[0])
O(N) (un-sorted) O(1) (sorted)
O(1)
Insert New Element
O(1) append()
O(log N) heappush()
Remove Minimum
O(N) pop(0)
O(log N) heappop()
Random Index Access (arr[i])
O(1)
O(1) (Returns arbitrary tree node, not i-th smallest)
Search by Value (x in arr)
O(N)
O(N)
Full Sort
O(N logN) sort()
O(N log N) [heappop() for _ in range(N)
SuperMade with Super