Consider the following recursive function: unsigned int foo(unsigned int n) { in

Question

Consider the following recursive function:

unsigned int foo(unsigned int n)

{

   int i, tralalala_pointless_for_loop = 0;

   if (n < 2) return 5;

   for (i = 0; i < n; i++)

     tralalala_pointless_for_loop++;

   return foo(n-2);

}

Which of the following recurrence relations most accurately represents the runtime of this function?

a)               Initial Condition: T(0) = T(1) = c0

                   Recurrence: T(n) = 5 + n for n 2

b)                Initial Condition: T(0) = T(1) = c0

                    Recurrence: T(n) = 5 + T(n) for n 2

c)                 Initial Condition: T(0) = T(1) = 5

                    Recurrence: T(n) = 5 + n for n 2

d)                Initial Condition: T(0) = T(1) = c0

                    Recurrence: T(n) = c1 + n for n 2

e)                Initial Condition: T(0) = T(1) = c0

                   Recurrence: T(n) = c1 + T(n) for n 2

f)                 Initial Condition: T(0) = T(1) = c0

                    Recurrence: T(n) = c1 + T(n-1) for n 2

g)                 Initial Condition: T(0) = T(1) = c0

                    Recurrence: T(n) = c1 + T(n-2) for n 2

h)                Initial Condition: T(0) = T(1) = c0

                    Recurrence: T(n) = c1 + n + T(n) for n 2

i)                  Initial Condition: T(0) = T(1) = c0

                    Recurrence: T(n) = c1 + n + T(n-1) for n 2

j)                  Initial Condition: T(0) = T(1) = c0

                    Recurrence: T(n) = c1 + n + T(n-2) for n 2

k)                 Initial Condition: T(0) = T(1) = c0

                    Recurrence: T(n) = c1 + n + 2·T(n-1) for n 2

Explanation / Answer

In this recursive function

unsigned int foo(unsigned int n) {

        int i, tralalala_pointless_for_loop = 0;

        if (n < 2) {
            return 5;
        }

        for (i = 0; i < n; i++) {
            tralalala_pointless_for_loop++;
        }

        return foo(n - 2);
}

If n<2, we are simply returning 5, which is constant operation
For every recursive call, we are iterating through all the elements which takes T(N) time.
Again we are invoking the function with n-2 as the argument which takes T(N-2)

So, total time complexity is given as,
Initial condition T(0) = T(1) = c0.
Recurrence : T(N) = c1 + N + T(N-2) for n>=2
So, answer is j

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.