How many total times will "i" and "1s" be printed in this recursion function using Master Theorem

Question

Function f(n):
 if(n>=1)
    for i=1 to n:
       print(i)
 f(n/2)
 f(n/2)

a)how many numbers will be printed b) how many times will 1 be printed Give your answers as a function of n. You can use the notation Θ(·) if it suits you. In each case, find the recursive relation of the required numbers and use the Master Theorem to solve it. We can assume that n=2^k, with k>=1.

i know that T(n)=2T(n/2)+ n and i found the time complexity for k=1: k=logb(a), then T(n) = Θ(n^k * log(n))=Θ(n*log(n)) for κ>1: k>logb(a), then T(n)= Θ(n^k) after that i m pretty much done i dont know what to do or how to find it

Answer 1

You are on the right track.

In a), the recurrence relation is T(n) = 2T(n/2) + n, because we print n numbers per iteration. Using the Master Theorem, we see that n = n^log_ba = n^log₂2 since a = 2, b = 2. Then, T(n) = Θ(n*log(n)) as you mentioned.

Hence, Θ(n*log(n)) numbers will be printed as a function of n.

In b), we note that for every iteration only one 1 will be printed, so the recurrence relation is T(n) = 2T(n/2) + 1. Using the Master Theorem, we see that 1 = n⁰ < n^log_ba, so we have T(n) = Θ(n).

Hence, Θ(n) 1s will be printed as a function of n.