Recently, I started to think of a problem involving the use of Twitter data that would involve finding pairs of users that participate in the most conversations. For example, with each tweet, you get the root conversation id along with a user id for that specific tweet. What I want to do is find pairs of users that participate in the same threads and also find the pair of users that have participated in the most threads (participation in a thread means that in one tweet, you would see a user id associated with the same conversation id as another user id.

This would involve first scanning every tweet (N) to fetch conversation, user id pairs. After doing this, I would have a list of user ids for each conversation id. I would then scan every user id association with each conversation id and then proceed to the next conversation id, scan each user id and compare against the previous list associated with previous conversation ids.

At the very least, I feel like the best method to do this would be, at a minimum, nlogn, but the method I'm proposing seems like it would make more comparisons than nlogn, but not as many as n^2.

How would I go about computing big O in this scenario?

Edit: I don't know if it is good form to edit one's question with a possible solution, but it appears you would need to scan each conversation (K) to get a list of tuples that associate users for that conversation (N^2-N)/2. You can then hash the tuple and increment the value of that dict key by one each time you discover the same tuple in another conversation. So ultimately you have to do (N^2-N) comparisons times K (each conversation). So the Big O would be larger than nlogn but not N^2. If I remember correctly, you drop the constants for big O so the running time would be somewhere around N^2-N \* K (for each conversation). I'm not sure how to correctly form the big O here (what do you do with K?).