How to calculate Run-Time efficiency of this program?

I'm a little new to Big-O analysis so I need some help!

How do you calculate big-O run-time efficiency of this program if the algorithm "doIT" has efficiency factor of 5n?:

for(i=1; i<=n; i++)
    doIT(...)

I feel like big-O run-time would be O(n^2) in this case, since the loop itself is O(n). Is this correct?

Upvotes: 0

Answers (2)

Reputation: 882586

Yes, that's correct. If doIT() is dependent on n itself then calling it within a loop also dependent on n makes the whole thing O(n²).

Upvotes: 1

Reputation: 2977

Using Sigma notation, you may do this:

enter image description here

Upvotes: 0