1

estou tendo dificuldade nesse exercício de complexidade de algorítimos, alguém pode dar uma luz?

Provar que, se f(n) = -n então f(n) é O(1).

Uma ideia que tive foi que para qualquer n positivo, f(n) será menor que n. Não sei se está correto

3
  • 2
    "para qualquer n positivo, f(n) será menor que n", não vejo como isso possa afetar a complexidade do algoritmo. No caso, acho que bastaria comentar que o número de operações executadas para calcular a saída é constante, portanto é O(1).
    – Woss
    Commented 26/08/2019 às 18:47
  • Acho que entendi seu ponto, mas e para "provar" isso? não teria que ter alguma linguagem matemática?
    – Bakun
    Commented 26/08/2019 às 18:52
  • @Bakun, basta mostrar que a quantidade de operações executadas não é afetada pelo tamanho do entrada. Isso é, por sinal, a definição de O(1) Commented 30/08/2019 às 17:40

1 Resposta 1

1

Tudo que f(n) faz é retornar -n. Calcular o negativo de um número é uma operação de complexidade constante, é igual para todos os números. E um algoritmo de complexidade constante (seja grande ou pequena) é O(1).

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .