Pandas三种连接时间复杂度存疑：测试显示均接近O(n)是否正确？

背景信息 #

我在Stack Overflow的帖子《What is the running time (big "O" order) of pandas DataFrame.join?》中了解到：内连接的时间复杂度应为O(n)，而左连接和右连接应为O(n log n)。

测试实现 #

我通过随机生成的DataFrame进行了测试，测试代码如下：

import pandas as pd
import numpy as np

df1 = pd.DataFrame({
        'user_id': range(1, size + 1),  # Unique user_id for df1
        'numeric_1': np.random.rand(size),
        'numeric_2': np.random.rand(size),
        'numeric_3': np.random.rand(size),
        'string_1': np.random.choice(['A', 'B', 'C', 'D'], size),
        'string_2': np.random.choice(['E', 'F', 'G', 'H'], size),
        'string_3': np.random.choice(['I', 'J', 'K', 'L'], size),
    })

df2 = pd.DataFrame({
        'user_id': range(size + 1, 2 * size + 1),  # Ensuring unique user_id for df2
        'numeric_4': np.random.rand(size),
        'numeric_5': np.random.rand(size),
        'numeric_6': np.random.rand(size),
        'string_4': np.random.choice(['M', 'N', 'O', 'P'], size),
        'string_5': np.random.choice(['Q', 'R', 'S', 'T'], size),
        'string_6': np.random.choice(['U', 'V', 'W', 'X'], size),
    })

针对不同样本量我多次模拟并取平均值，以此降低本地环境差异的影响。

测试结果与疑问 #

测试得到的图表显示三种连接的曲线接近平行，斜率约为1.07，由此我认为三种连接的时间复杂度均为O(n^1.07)，非常接近O(n)。

请问这个结论是否正确？若左/右连接确实是O(n log n)，图表会呈现怎样的特征？如需完整测试代码，我可以提供。

内容的提问来源于stack exchange，提问作者user1029384756