Big O - is n always the size of the input?

Question

I made up my own interview-style problem, and have a question on the big O of my solution. I will state the problem and my solution below, but first let me say that the obvious solution involves a nested loop and is O(n²). I believe I found a O(n) solution, but then I realized it depends not only on the size of the input, but the largest value of the input. It seems like my running time of O(n) is only a technicality, and that it could easily run in O(n²) time or worse in real life.

The problem is: For each item in a given array of positive integers, print all the other items in the array that are multiples of the current item.

Example Input:

[2 9 6 8 3]

Example Output:

2: 6 8
9:
6:
8:
3: 9 6

My solution (in C#):

private static void PrintAllDivisibleBy(int[] arr)
{
    Dictionary<int, bool> dic = new Dictionary<int, bool>();
    if (arr == null || arr.Length < 2)
        return;

    int max = arr[0];
    for(int i=0; i<arr.Length; i++)
    {
        if (arr[i] > max)
            max = arr[i];
        dic[arr[i]] = true;
    }

    for(int i=0; i<arr.Length; i++)
    {
        Console.Write("{0}: ", arr[i]);
        int multiplier = 2;
        while(true)
        {
            int product = multiplier * arr[i];
            if (dic.ContainsKey(product))
                Console.Write("{0} ", product);

            if (product >= max)
                break;
            multiplier++;
        }
        Console.WriteLine();
    }
}

So, if 2 of the array items are 1 and n, where n is the array length, the inner while loop will run n times, making this equivalent to O(n²). But, since the performance is dependent on the size of the input values, not the length of the list, that makes it O(n), right?

Would you consider this a true O(n) solution? Is it only O(n) due to technicalities, but slower in real life?

Answer 1

Good question! The answer is that, no, n is not always the size of the input: You can't really talk about O(n) without defining what the n means, but often people use imprecise language and imply that n is "the most obvious thing that scales here". Technically we should usually say things like "This sort algorithm performs a number of comparisons that is O(n) in the number of elements in the list": being specific about both what n is, and what quantity we are measuring (comparisons).

If you have an algorithm that depends on the product of two different things (here, the length of the list and the largest element in it), the proper way to express that is in the form O(m*n), and then define what m and n are for your context. So, we could say that your algorithm performs O(m*n) multiplications, where m is the length of the list and n is the largest item in the list.