0

I'm currently working on a project for school in which I have a time complexity restriction. I'm still beginning to learn to program so apologies of this question is stupid.

Essentially, lets say I have a constraint that my program must satisfy the time complexity O(n^2 + mlogm), where n and m are some sizes of input. Does that mean that's the maximum time complexity any specific component of my program can run in? That is, if I have a ton of, say, O(n^2 + m) functions, but the most complex function runs in O(n^2 + mlogm), will I still satisfy this time bound? For example, if my program runs the following functions in order

functionA

functionB

functionC

functionD

And functions A, B, C are all O(n^2 + m) or something less than the time complexity restraint, but the last function is O(n^2 + mlogm), will my program be within the time constraint? Would that not somehow be O(n^2 + m ^ n^2 + m ^ n^2 + m + n^2 + mlogm) for the overall complexity?

I'm still learning about time complexity, so any help for this would be much appreciated. Thanks a bunch.

tmako
  • 349
  • 2
  • 9
  • 1
    Would referring to this [time-complexity cheat-sheet](https://www.bigocheatsheet.com/), or perhaps better yet, this [more general discussion about time-complexity](https://stackoverflow.com/q/11032015/645128) help? – ryyker Nov 28 '20 at 00:20
  • @ryyker Didn't see that general dicsussion, that is exactly what I needed. Thank you! – tmako Nov 28 '20 at 00:23

1 Answers1

3

If you're executing different functions in sequence, you just choose the worst complexity and that's the overall complexity.

For example, if fnA was O(n) and fnB was O(nn!), then any effect of fnA would be totally swamped by fnB, assuming they're run sequentially (not nested).

In your case, the final of your functions meet the requirement and the first three are better, so the overall complexity is that of the final one.

paxdiablo
  • 854,327
  • 234
  • 1,573
  • 1,953
  • Thank you so much! – tmako Nov 28 '20 at 00:23
  • 1
    @tmako please don't delete questions after receiving answers to them, that is disrespectful to paxdiablo, not to mention destructive behavior as far as the site is concerned. – cs95 Dec 18 '20 at 09:55