What is the best runtime characterization of an efficient implementation of the following function:

static $KVvv>>$ invert$(HashMap$ map$)$

This function takes $as$ input a map $of$ key$-$value pairs. Keys are type $\text{'}K\text{'},$ and values are type $\text{'}V\text{'}.$

$It$ should return a map where the keys $of$ the new map are values from the input map. For any value $\text{'}v\text{'}$ contained $in$ the input

map, the associated value $in$ the returned map for key $\text{'}v\text{'}isan$ 'ArrayList' $of$ keys from the input map that had that value.

Select one:

constant

quartic

cubic

quadratic

linear