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

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.

• multiplication operation is a function of input, n. That is why input will have change in time complexity of multiplication Feb 5, 2020 at 16:30
• You have two different n’s. It would be very strange to have a multiplication where the time complexity depends on the list size. Feb 5, 2020 at 16:48

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.