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:

1- thread ids

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?


  • 1
    $\begingroup$ Sorting takes $O(n\log n)$, unless you are using some tricks. $\endgroup$ – Yuval Filmus Apr 3 '17 at 7:15
  • $\begingroup$ 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! $\endgroup$ – DanAl Apr 3 '17 at 7:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.