As I understand, the complexity is not much worse than O(A * K), where A is upscaled image area and K is approximate KNN lookup time in a dataset of all tiles f

As I understand, the complexity is not much worse than O(A * K), where A is upscaled image area and K is approximate KNN lookup time in a dataset of all tiles for all scales. The question is, how fast is KNN on such high-dimensional data.