Running time of an algorithm

[athrun200]

Homework Statement

Suppose I have n activicties and I want to join them as much as possible without time crash.
We are provided the following algorithm.

(1)Consider events in increasing order of finish time
(2)Start with the first event on the sorted list
(3)Include an event if it is compatible with the ones selected so far
(4)Repeat from(3)for the next event on the list until the whole event list is checked.


Question:
What is the running time of the algorithm? Express it in terms of n.

Homework Equations

The Attempt at a Solution

The time needed for:
Step(1) is n since it checks n events.
(2) is 0. I think that action requires no time.
(3)n-1. You use 1 time to compare 2 event, 2 time to compare 3 event...so n-1 time to compare n event
(4) It repeat (3), suppose we have discarded i events then running time is n-i-1
Repeat (3) again, suppose we discarded another j events then running time is n-j-i-1


The total running is the sum of these time.
However the question is how many time with step 4 repeat?

If I don't know the times of repeat, I can't sum them up.

 

[KataKoniK]

Your approach is on the right track, but there are a few things to clarify.

First, in step (2) it is true that there is no actual action being taken, but we still need to consider the time it takes to move to the first event on the sorted list. This can be done in constant time, so we can say step (2) takes O(1) time.

Second, in step (3), you are correct that it will take n-1 comparisons to determine if an event is compatible with the ones selected so far. However, this step will be repeated for each event, so we need to consider the total number of events that are being checked. This can be expressed as the sum of the first n-1 positive integers, which is equal to (n-1)(n)/2. Therefore, we can say that step (3) takes O(n^2) time.

Finally, in step (4), we need to determine how many times step (3) will be repeated. This will depend on the specific order of events and which ones are compatible with each other. In the worst case scenario, where no events are compatible, step (3) will be repeated n-1 times. In the best case scenario, where all events are compatible, step (3) will only be repeated once. So, we can say that step (4) takes O(n) time.

Overall, the running time of the algorithm can be expressed as O(n^2) if we consider the worst case scenario for step (4). However, if we assume that on average, step (3) will only be repeated a constant number of times, then the running time can be expressed as O(n).

I hope this clarifies the approach to finding the running time of the algorithm.