Informal Run-Time Analysis Practice Test

A program searches an unsorted list of $n$ usernames to find a target name.

public static int findUser(String[] users, String target) {

    for (int i = 0; i < users.length; i++) {

        if (users<u>i</u>.equals(target)) {

            return i;

        }

    }

    return -1;

}

How does the run-time of this algorithm change as the input size doubles?

A recursive method computes the $n$th Fibonacci number for small $n$ in a math game.

public static int fib(int n) {

    if (n <= 1) {

        return n;

    } else {

        return fib(n - 1) + fib(n - 2);

    }

}

Which of the following best describes the algorithm's time complexity?