Indique se a seguinte afirmação é verdadeira ou falsa.

Um algoritmo que tem tempo de execução T( n ) = 1000n+ n ² +10  tem complexidade temporal O ( n² )

//

Indicate whether the following statement is true or false.

An algorithm that has a running time of T( n ) = 1000n+ n ² +10 has time complexity O ( n² )

Qual a complexidade temporal do método allDiff no pior caso? //

/**
     *
     * @param numbers : an array that is filled up to position n-1 
     * @return true iff all the numbers are different
     */
    public static boolean allDiff(int[] numbers,int n) {
        int i=0;
        while (i<n && diff(numbers[i],numbers,i,n))
            i++;
        return i==n;
    }
    private static boolean diff(int number, int[] numbers, int pos, int n) {
        int i=pos+1;
        while (i<n && number!=numbers[i])
            i++;
        return i==n;
    }

Qual a complexidade temporal do método allEqual no pior caso? // 
What is the worst-case time complexity of the method allEqual?
/**
 *
 * @param numbers : The array is completely full.
 * @return
 */
public static boolean allEqual(int[] numbers) {
    int x=numbers[0];
    int i=1;
    while (i<numbers.length && x==numbers[i])
        i++;
    return i==numbers.length;
}

Qual das situações representa um cenário de melhor caso do método allEqual? //
Which situation represents a best-case scenario for the method allDEqual?
/**
 *
 * @param numbers : an array that is completely full
 * @return
 */
public static boolean allEqual(int[] numbers) {
    int x=numbers[0];
    int i=1;
    while (i<numbers.length && x==numbers[i])
        i++;
    return i==numbers.length;
}

Qual das situações representa um cenário de pior caso do método allEqual? //
Which situation represents a worst-case scenario for the method allEqual?
/**
 *
 * @param numbers : The array is completely full
 * @return
 */
public static boolean allEqual(int[] numbers) {
    int x=numbers[0];
    int i=1;
    while (i<numbers.length && x==numbers[i])
        i++;
    return i==numbers.length;
}

Considere um algoritmo que tem taxa de execução T( n ) = 10ⁿ + 1000 n²

Este algoritmo é (escolha todas as opções correctas).

//

Consider an algorithm that has execution rate T( n ) = 10ⁿ + 1000 n²

Imagine que tem um programa P implementado, que recebe como input n

números. Ao experimentar executá-lo com testes aleatorizados, obteve os seguintes tempos de execução:

• Com n=100

  demorou 0.5 segundos

• Com n=200

  demorou 4 segundos

• Com n=400

  demorou 32 segundos

Qual será a complexidade temporal mais provável do programa P?

//

Imagine you have an implemented program P, which receives n numbers as input.

Qual situação representa um cenário de pior caso do método allDiff? // 
Which situation represents a worst-case scenario for the method allDiff?
/**
     *
     * @param numbers : an array that is filled up to position n-1 
     * @return true iff all the numbers are different
     */
    public static boolean allDiff(int[] numbers,int n) {
        int i=0;
        while (i<n && diff(numbers[i],numbers,i,n))
            i++;
        return i==n;
    }
    private static boolean diff(int number, int[] numbers, int pos, int n) {
        int i=pos+1;
        while (i<n && number!=numbers[i])
            i++;
        return i==n;
    }

Indique se a seguinte afirmação é verdadeira ou falsa.

Um algoritmo que tem tempo de execução T( n ) = 2n² +3n + 2 tem complexidade temporal O ( n ).

//

Indicate whether the following statement is true or false.

Qual a complexidade temporal do método allEqual no melhor caso, sendo n=numbers.length? //
What is the best-case time complexity of the method allEquals, where n=numbers.length?
/**
 *
 * @param numbers : array that completely full
 * @return
 */
public static boolean allEqual(int[] numbers) {
    int x=numbers[0];
    int i=1;
    while (i<numbers.length && x==numbers[i])
        i++;
    return i==numbers.length;
}