What would be the big O notation for a function that attempts to find pairs of users that participate in different discussions?

Question

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?).

Answer 1

It might be nice to model the problem as a bipartite graph $(U, C, E)$ where $U$ is the set of users, $C$ is the set of conversations, and $E \subseteq U \times C$ are edges for participation.

In this setting, for each user, the set of other users that participate in the same conversations are its neighbors-of-neighbors. Let's make a new graph where each user is connected to its neighbors-of-neighbors. In the new graph, give each edge a weight which is the number of unique conversations in which those two users participate. This can all be computed in O(|E|) because each edge in the new graph corresponds to two edges of the original.

In the new graph, look at the edge with the largest weight. The endpoints are the pair of users that converse the most with each other.

(I think this is approximately the algorithm that you had in mind. Using a bipartite graph makes things clearer.)

All together, that gives you O(|E|) for computing the result. I don't think there's any other algorithm that can do better than $O(|E|)$ in the worst case.

EDIT: this is too slow, because the new graph can be huge, much larger than |E|. See comments.

Answer 2

It's a bit pedantic, but problems and functions don't have big-O representations, algorithms do. There are many algorithms that could implement the function you describe, and they have different big-O performance. It's confusing, because generally people want the fastest algorithm for a given problem, so you'll hear things like "sorting is n*log(n)", which is not formally true.

The second thing to think about for your problem is "What does N represent?"

In a problem where there are several "sizes", it's perfectly reasonable to use different letters to represent different things. So let's say that there are N conversations and the longest one is M posts long.

An algorithm to generate your answer (ignoring a lot of details) could look something like:

# maps every pair to the number of conversations they've shared. e.g. "alice$bob" -> 10
pair_frequency = dict()
for convo in conversations:
  for tweet in convo:
    for other_tweet in convo:
      pair_frequency[tweet.userid + "$" + other_tweet.userid] += 1

# which pair is most frequent?
max = 0
max_pair = null
for pair, freq in pair_frequency:
  if freq > max:
    max = freq
    max_pair = pair
return max_pair

This algorithm is O(N * M^2), since, for each tweet in each conversation, it iterates over every other tweet in the conversation.

This might or might not be a good algorithm for you to actually use, but it's how I would start thinking about the problem in terms of big-O.

Something to think about - in reality, it's probably important to know the average number of tweets in a conversation, but for big-O analysis I chose M to be the length of the longest thread.