Writing and solving a recurrence for this algorithm that counts prime numbers?

Question

I'm studying for a test and I came across this question, I'm not too great at this course and I'm completely stumped by it. I would really appreciate some help!

Suppose you have access to an algorithm isprime(n) which runs in time O(n) (say, a brute force checking divisibility by all numbers less than n). The following code calculates the number of primes less than or equal to its input argument.

boolean numprimes(int n) {
    if (n == 1) {
        return 0;
    } else if (isprime(n)) {
        return numprimes(n − 1) + 1;
    } else {
        return numprimes(n − 1);
    }
}

The goal is to analyze the runtime of num primes. Achieve this goal by doing the following:

(a) Write a recursive definition for T (n) the running time of the algorithm on an instance of size n.

(b) Solve the recursive definition of T (n) to acquire a closed form using the method of repeated substitutions, making a guess, proving the guess by induction, and the finally deducing a closed from based on your guess. Alternatively, you can use repeated substitutions to guess a closed form, and prove your closed form correct by induction.

Thanks a lot, I will really appreciate any help!

Answer 1

As a hint, here's what the recurrence looks like:

T(1) = 1

T(n) = T(n - 1) + O(n)

This holds because there's always one recursive call made (on an input of size n - 1), and each individual call does O(n) work.

If you rewrite this as

T(1) ≤ 1

T(n) ≤ T(n - 1) + kn

You can start iterating. As a hint, the final result should be O(n²); I'll leave the details to you.

Hope this helps!

Answer 2

a) Since the test for prime is performed in O(n) time, the recurrence will be

T(n) = T(n-1) + O(n)

b) With part a solved, the rest should be easy enough. I can help you more if you show me what you have done to solve this.