O-big notation and the complexity of social interactions

    If you had to sit in an unbearably boring meeting, where two people discuss the problem, and everyone else is the audience, you are ready to accept the idea that this method of interaction is not effective. You may also have thought of alternatives. The mistake of the organizers of the meeting was that they chose a form of interaction that was not appropriate for the task, and, thereby, doomed a large number of people to waste time.

    Some time ago, I realized that in assessing the complexity of social interactions, you can apply the same approaches as in assessing the complexity of algorithms - which means you can see their pros, cons and applications. Below is a short list of the most common options I've dealt with.

    O (n 2 ): Meeting of equal participants. npeople discuss the issue, and to achieve mutual understanding, each participant needs to communicate with everyone. In total, n * (n-1) / 2 social interactions will be carried out (equivalent to the task of calculating the number of handshakes in a group of n people), i.e., the complexity of the O (n 2 ) algorithm . It would seem that due to the fact that n / 2 pairs of people can communicate at the same time , the time score is O (n) , however, in real meetings, only one person speaks at a time, so the worst-case score is O (n 2 ). If the interaction time is 5 minutes and two iterations are required in order to achieve full understanding in the group, then the meeting of three people will last 30 minutes, four - an hour, five will take 1 hour 40 minutes to find a common solution (which suspiciously seems to be true). If the number of iterations depends on the number of participants, we get even more sad estimates.

    But it is not all that bad!

    - Firstly, not all participants in the meeting can be independent and equal, they can form interest groups (for example, a boss and his two subordinates), then the discussion does not take place between individual participants, but between groups, the representative of which is always one person. The representative may change during the discussion, but he is always only one. In this case, the complexity of social interaction isО ((n / m) 2 ) , where m is the average number of participants in each group present at the meeting.

    - Secondly, O (n 2 ) is the worst rating. It may turn out that each side expresses its position in turn, and each next builds its statement taking into account all that has been heard earlier. The last participant offers a solution to the problem - and all participants in the discussion agree with him or make their minor changes. In this case, only 2n actions are enough to make a decision . Morality: a prepared presentation and a moderator determining the order of discussion can save a lot of time.

    About (n * log (n)):team decision making through delegates. Often, decision-making requires attracting a lot of people. The solution may cover a technically complex area or the implementation may require the efforts of a large number of people. After the task is set, each of the participants proposes a solution to his part of the task, setting it out to the delegate (for example, the head of his department). The delegate summarizes the proposals received and presents them to the delegate of the second level (chosen among the delegates of the first level), who, in turn, summarizes the proposals received and presents them to the delegate of the third level - and so on. Continuing the algorithm recursively and reaching the person making the final decision, we get an option that, to one degree or another, will take into account the opinion of each of the participants.O (m * log m (n)) , where m is the characteristic number of people in the group.

    O (n): chain of coordination. Often there is already a solution, you just need to go through a standardized procedure for its approval. For example, to coordinate the addition of a new product to a shelf. Here, the complexity of one attempt will be equal to n , where n is the number of instances that will need to be passed. Yes, the number of attempts is not limited in any way, but since the requirements are known in advance; it is usually small.

    O (n): alert. Ideal for situations where you need to bring some information unchanged to a large number of people. Each of the group will spend time familiarizing themselves, so the labor costs will be nsocial interactions. In bad cases, the method may take the form “I ask you to familiarize yourself with the order and accept it for execution,” in good cases it’s just a check for the correctness of the data prescribed in the code. The differences between these cases are in the number of people who will actually encounter a notification (in the second - much less), as well as in the differences in the requirements for the artist’s memory (in the second - it is not necessary to remember at least something until the restriction works). But, personally, I like this approach that it is O (1) in time for the sender - the labor costs will remain unchanged regardless of the number of people who receive the message. The dark side of the same rule is letters with dozens of people in a copy.

    About (log (n)):Notification through delegates. Used when only one person needs to be notified, but it is not known who exactly. An example is a task that comes down to management, then is transferred to the head of the department, then to the direct executor. An alternative way is to create a “single window” through which all tasks / orders / wishes are accepted. This method of setting the task is still constant in complexity for the sender, but much less labor-consuming for the receiving side, therefore it is the receiving side, as a rule, who initiated the change of the exchange method from “notification” to “notification through delegates”.

    About (1):solution to the problem through a standard interface. An ideal situation which, in my opinion, should be sought. The problem is known, as are the ways to solve it, which means that you can create an interface that will help a person solve his problem without any contact with other people, and the speed of solving the problem does not depend on the number of people who have encountered it. We can say that this is the same “alert”, but from the point of view of the sender, and the real costs from users are still O (n) . This is so, but I decided to single out this method, because, despite the mathematical equivalence, it gives a new look at the problem.

    Are there ways to interact with the outside world with complexity worse than O (n 2 ) ? Definitely yes - similar toSwamp sorting can come up with options that will be terribly impractical. I believe that they are not found in practice only because all real problems are solved by less labor-intensive algorithms.
    If there are approaches in which the problem is solved in constant time - then why are all other methods needed? I believe that the main reason is the freedom of decision-making. Along with the improvement of the asymptotic behavior, freedom is gradually leaving. In a meeting of equal participants, the range of decisions is limited only by the powers of the people participating in the meeting. This tool is well suited for making important unique decisions. When using standard interfaces, the range of solutions is significantly narrowed.

    Practical implications:

    - Do not call more than 5 people for meetings of equal participants. If the time of one interaction between people is 5 minutes, most likely you will not meet the 1 hour of discussion.
    - don’t call more than 15 people for meetings of unequal participants (5 bosses + 2 subordinates on each side) - again you don’t have one hour — do
    n’t call people who need only “ok” to write to the meeting - write the minutes of the meeting and ask agree
    - orders, instructions, informational messages (and possibly the next voting) - the only effective way to communicate, if interested parties more than a few tens
    - if the department more than 10 people - create a "single window" where are proceeding in s standard requirements / suggestions / requests.
    - if you or your employees do not have time to complete the tasks that come to them - think about whether you can improve the asymptotic behavior by changing the way you interact with the outside world.

    Ps Unfortunately, the speed of interaction between people does not double every two years.
    Optimize your communication and be happy.

    Also popular now: