(adsbygoogle = window.adsbygoogle || []).push({}); 1. The problem statement, all variables and given/known data

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.

2. Relevant equations

3. 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.

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Running time of an algorithm

Can you offer guidance or do you also need help?

Draft saved
Draft deleted

**Physics Forums | Science Articles, Homework Help, Discussion**