# Algorithm to construct timeline graph with arrival and departure times

So I am trying to construct a timeline graph for threads interacting with synchronization functions e.g. pthread_mutex_lock.

I have the following information:

2- ids for the synchronization functions

3- Arrival times of the threads at the synchronization functions e.g. the time at which the thread encountered pthread_mutex_lock

4- Crossing time i.e. the time at which the thread crossed in to the critical section (e.g. crosses pthread_mutex_lock)

My idea:

1- Sort all the times (both arrivals and crossings)

2- for each time construct the event i.e. thread x arrived/crossed at synchronization y.

The questions:

1- The time complexity for this will be O(n log n) where n is the number of events (i.e arrival and crossing)?

2- Any possible imporvements/alternative ways/existing algorithms?

cheers!

• Sorting takes $O(n\log n)$, unless you are using some tricks. – Yuval Filmus Apr 3 '17 at 7:15
• oh true, probably my brain wasn't functioning properly, so I thought O(n) is larger than O(nlogn). Let me fix it in the question. Thanks! – Dev2017 Apr 3 '17 at 7:17