---
id: Complexity
aliases:
  - Computational/Time Complexity
tags: []
---

## Computational/Time Complexity

- K-Medoids:
  - PAM: $O(K(n - k)^2)$
- Kernel K-Means:
  - Computational complexity (time and space) is higher than K-Means
    - Need to compute and store n x n kernel matrix generated from the kernel
      function on the original data, where n is the number of points
- Hierarchical Clustering:
  - Agglomerative Clustering
    - Time complexity: $O(n^2)$
    - Algorithmic Complexity: $O(m^2logm)$
- Density-based Clustering:
  - DBSCAN:
    - Computational complexity: $O(nlogn)$
      - worst case: $O(n^2)$
  - OPTICS:
    - Complexity: $O(NlogN)$