CODEWITHSUNDEEP
performancealgorithmtime-complexity
1337holiday
1337holiday

Reputation: 1954

Analyze Run time of nested for loop

I'm having some issues determining if this nested for loop runs in O(n) or O(n^2).

Suppose I have a list of performances P and each performance has a duration (# of hours). 

P = [P1, P2, ...., Pn]
for p in P:
    for hour in p.hours:
        //do stuff here
    end
end

What would be considered the running time of this? I know the total number of executions would be the sum of all the hours in each performance or O(totalHours) but is this linear or polynomial? Keep in mind the # of hours can vary from performance to performance and can be arbitrarily large or small.

Upvotes: 0

Views: 60

Answers (2)

Bernhard Barker
Bernhard Barker

Reputation: 55589

I'd probably say it's O(mn), where n is the number of performances and m is the average number of hours per performance (or, as you say, O(totalHours)).

It's linear in the total number of hours.

Since it's not only dependent on the number of performances, I don't believe you can say it's linear (or even polynomial, for that matter) in that (even though the power of n is 1 in the above complexity) (but opinions may vary here).

Upvotes: 1

Jon
Jon

Reputation: 437336

It's linear on the total number of hours in the input. If that number cannot be expressed as a function of the number of performances then you can't link the running time to the number of performances.

Upvotes: 1

Related Questions