Which algorithm complexity depends on n or k and what does it depend on?

In machine learning and algorithms, parameters n and k are often encountered, affecting the complexity of the algorithm:

• n usually denotes the size of the input data (for example, the number of objects, features, elements).
• k is often used to denote the number of clusters, neighbors (in k-NN), or other model parameters.

The complexity of the algorithm depends on how exactly it processes these parameters:

• If the algorithm iterates over all objects, its complexity is often expressed as O(n).
• If the algorithm requires comparing each object with k elements (for example, k nearest neighbors), the complexity can be O(n*k).
• In clustering algorithms (for example, k-means), the complexity depends on the number of iterations, the size of the data n, and the number of clusters k, often O(nki), where i is the number of iterations.

Thus, the complexity depends on what operations are performed and how they scale with increasing n and k. For example, increasing k in k-NN will increase the computations for each object, and increasing n will increase the total number of objects to process.