-1
$\begingroup$

Suppose I want to deploy the algorithm for finding connected components in a graph $k$ many times. Now the time complexity for finding connected components in an undirected graph is $O(v+e)$. Then what will be the time complexity, $O(k(v+e))$ or $O(ke)$?

Similarly, I have deployed a method $k$ times which requires $O(n^2+n^2)$. What will be its complexity, $O(kn^2)$ or $O(k(n^2+n^2))$?

$\endgroup$
4
0
$\begingroup$

It is possible that an algorithm gathers information when it's running and doesn't throw it away. If gathering that information takes O(n^2) but solving the problem with the help of the information gathered only takes O(n), then solving the same problem k times could run in O(n^2 + kn). All depends on your algorithm.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.