1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?