Considere um conjunto de sapatos, de mesmo modelo e que estão todos misturados. Para cada sapato, é possível saber o número e se ele corresponde a um pé direito ou esquerdo. Avalie as seguintes soluções algorítmicas para saber se há algum sapato sem par.

I. Utiliza-se de uma variável composta heterogênea unidimensional que armazena o número do sapato e se ele corresponde a um pé direito ou esquerdo. Ordena-se a variável composta pelo número dos sapatos. Depois, para um dado número de sapato, busca-se formar os pares direito-esquerdo, mudando-se as células de posição. Ao final, é possível verificar as células que não formam pares.

II. Utiliza-se de duas variáveis compostas homogêneas unidimensionais, com índices correspondentes aos números dos sapatos. Uma variável composta armazena a quantidade de sapatos para pés direitos e a outra a quantidade de sapatos para pés esquerdos. Ao final, estão sem par aqueles sapatos cujas células de mesmo índice têm dados diferentes.

III. Utiliza-se uma variável composta homogênea bidimensional, com índices que correspondem aos números dos sapatos em uma dimensão e índices que correspondem ao pé, direito ou esquerdo, na outra dimensão. Armazena-se a quantidade de sapatos em cada célula, considerando o número do sapato e o pé correspondente. Percorre-se a variável composta, subtraindo-se os dados da primeira linha, daqueles da segunda linha, para colunas correspondentes. Ao final, estão sem par os sapatos em que o resultado da subtração é diferente de zero.

Com relação à complexidade no tempo (número de comparações), no pior caso, simbolizada pela notação O (O-grande), marque a alternativa correta.