Time complexity of $O(n)$ loop which has a multiplication ($O(n^2)$) in it

Question

Assume we know that the implementation for the multiplication operator for a language is known to be $O(n^2)$.

Given this pseudocode:

func wibble_wobble(List<Integer> input):
    Integer constant = input.length;
    return List<Integer> { item * constant foreach item in input };

Since the loop inside the new list initialization is $O(n)$, but the multiplication operation inside is $O(n^2)$, is this function considered to have a time complexity of $O(n)$, $O(n^2)$, or maybe even $O(n*n^2)=O(n^3)$?

My gut instinct says it is $O(n)$ because a change in input would not change the time complexity of the multiplication operation, and thus would not need to be considered, but I am not sure.

Answer 1

The problem is that you are using $n$ to mean too many different things without really defining it. You can't say that an algorithm runs in $O(n)$ time without specifying what $n$ is, unless it is clear from context. In this case it is not clear, and that is what is tripping you up.

When we say an integer multiplication algorithm runs in $O(n^2)$ time, the tacit assumption is that $n$ is the number of bits in the two input arguments. In practice, a multiplication algorithm that runs in $O(n^2)$ is usually actually a multiplication algorithm that runs in $O(pq)$, where $p$ is the number of bits in the first argument and $q$ is the number of bits in the second argument.

When analyzing an algorithm such as the one in the question, it would be typical to define two variables: the number of elements in the list (let's call it $\ell$) and the maximum size of any element of the list (let's call it $s$). The bit size of the representation of $\ell$ is $\Theta(\log \ell)$. Given this information—and the assumption above that the multiplication algorithm runs in time $O(pq)$ for input bit sizes $p$ and $q$—then the runtime analysis is easy: the function runs in time $O(\ell s \log \ell)$.

It is possible to do runtime analysis on this procedure using only a single $n$ variable, if we define $n$ to be the total number of bits in the representation of the entire input. That is, we let $n$ be the sum of the bit lengths of all the integers in the input list. Since $\ell$ and $s$ above are obviously no greater than $n$, we can substitute $n$ for $\ell$ and $s$ in our previous bound to get a weak bound of $O(n^2 \log n)$. A more detailed analysis can actually prove $O(n \log n)$, since each bit of the input is only used in one left-hand side of a multiplication.

However, if we also drop the $O(pq)$ multiplication assumption and assume only the guarantee stated in the question of $O((\max\{p, q\})^2)$, then trying to get a bound better than $O(n^3)$ requires a lot more fiddly reasoning about tradeoffs between element size vs. list size, and probably isn't worth it. [*]

The moral of the story: when analyzing an algorithm whose runtime is affected by multiple factors, state your definitions clearly, and use as many variables as necessary for a straightforward analysis unless there is a strong reason to lump things together.

---

[*] This is based on me thinking about the problem for all of 5 minutes. Maybe someone else can volunteer a proof of $O(n^2)$ under these assumptions, but I couldn't think of one.