def estimate_upper_bound_cache_size_in_nb_of_integers(nb_of_rules) -> int:
    """
    Estimate an upper bound for a the size of the cache.

    The cache maps a rule pair sharing at least 1 attribute in their heads to two integer values.
    A key into the cache is also two integers.

    Assume there are n rules.
    If they are ordered,
        rule 1 has to be compared with n-1 rules
        rule 2 with n-2 rules
        ...
        rule n with 0 rules
    --> (n²-n) / 2 possible rule pairs.

    In the absolute worst case, each rule has a shared target attribute with each other rule.
    An upper bound for the nb of integers necessary for the cache is:
        4 * (n²-n) / 2 = 2 (n²-n)
    :param nb_of_rules:
    :return:
    """

    return 2 * (nb_of_rules ** 2 - nb_of_rules)