def dummy_linearithmic_function(n):
    # Dummy operation with linearithmic complexity.

    # Constant component of linearithmic function
    dummy_constant_function(n)

    x = 0
    log_n = int(np.log(n))
    for i in range(n):
        for j in range(log_n):
            for k in range(20):
                x += 1
    return x // 20

    def test_big_o(self):
        # Each test case is a tuple
        # (function_to_evaluate, expected_complexity_class, range_for_n)
        desired = [
            (dummy_constant_function, compl.Constant, (1000, 10000)),
            (dummy_linear_function, compl.Linear, (100, 5000)),
            (dummy_quadratic_function, compl.Quadratic, (1, 100)),
            (dummy_linearithmic_function, compl.Linearithmic, (10, 5000)),
        ]
        for func, class_, n_range in desired:
            res_class, fitted = big_o.big_o(
                func, datagen.n_,
                min_n=n_range[0],
                max_n=n_range[1],
                n_measures=25,
                n_repeats=1,
                n_timings=10,
                return_raw_data=True)

            residuals = fitted[res_class]

            if residuals > 5e-4:
                if isinstance(res_class, class_):
                    err_msg = "(but test would have passed)"
                else:
                    err_msg = "(and test would have failed)"

                # Residual value is too high
                # This is likely caused by the CPU being too noisy with other processes
                # that is preventing clean timing results.
                self.fail(
                    "Complexity fit residuals ({:f}) is too high to be reliable {}"
                    .format(residuals, err_msg))

            sol_class, sol_residuals = next(
                (complexity, residuals) for complexity, residuals in fitted.items()
                if isinstance(complexity, class_))

            self.assertIsInstance(res_class, class_,
                msg = "Best matched complexity is {} (r={:f}) when {} (r={:f}) was expected"
                    .format(res_class, residuals, sol_class, sol_residuals))