1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ multiplication operation is a function of input, n. That is why input will have change in time complexity of multiplication $\endgroup$ – Breakpoint Feb 5 '20 at 16:30
  • 3
    $\begingroup$ You have two different n’s. It would be very strange to have a multiplication where the time complexity depends on the list size. $\endgroup$ – gnasher729 Feb 5 '20 at 16:48
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.