3

I have 3 algorithms (A1, A2 and A3) and their estimated time complexities are O(n Log n), O(K n) and O(Q n) respectively, where K and Q are different parameters of the actions. Then I have a fourth algorithm that runs those 3 algorithms consecutively (each one needs the results of the previous).

I'm confused about how should I estimate the total complexity of the suite of algorithms. As far as I can understand, O(n Log n) grows faster than O(K n) and O(Q n), therefore the most important part in terms of time consumption will be A1 and probably that will be the most relevant behavior for a n big enough. But that won't reflect that even after A1 is done, still A2 and A3 will take a lot of time.

So I was wondering, how should I account for that? Is it enough by just saying the complexity is O(n Log n)?

Rodrigo
  • 231
  • 3
  • 16

1 Answers1

4

The total time complexity is:

O(n Log n) + O(K n) + O(Q n)

which if assumed that K and Q are parameters that grow slower than or similarly to Log n, then the total time complexity is:

O(n Log n)

since we are using big-o notation. Otherwise the total time complexity is the initial sum (or part of it).

The idea is to keep the term that will dominate the other term(s) when n grows.

gsamaras
  • 71,951
  • 46
  • 188
  • 305