Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Running time of an algorithm

  1. Oct 7, 2011 #1
    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.
     
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted