Я предполагаю, что вы хотите сложность времени этого алгоритма. Поскольку временная сложность - это НЕ сколько времени на самом деле занимает алгоритм, а сколько операций требуется для него (следует цитата, подтверждающая это утверждение), временная сложность этого алгоритма равна O(n^2), как если бы он не был параллельным ,
со страницы вики: Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, where an elementary operation takes a fixed amount of time to perform
Почему нас не волнует тот факт, что алгоритм параллелен?
Обычно размер нашего кластера фиксирован и не зависит от ввода [n]. пусть размер кластера будет k [это означает, что мы можем выполнять k операций одновременно, а алгоритм равен O(n^2) [для простоты предположим, что точно n^2]
предположим, что у нас есть вход размером 100, тогда это займет "1017 * время. если бы он был размером 1000, это заняло бы (1000^2)/k, а для n элементов: (n^2)/k, как вы можете видеть, k является константой, и тот факт, что программа параллельна, не меняет сложности. Возможность одновременно выполнять k операций не лучше [и даже не стоит, но это для другого потока], чем компьютер * на 1021 * раз быстрее.