Question

Function F(n)
if n > 1 then
for i = 1 to n
Print “Hello”
  for i = 1 to 10
  F(n/3)

  How often is written "Hello" as a function of n? Set up as an equation and solve it

Answer 1

assuming T is a function of number of times Hello is printed
T(n) = 10T(n/3) + n
and T(1) = 0

Answer 2

To determine how often "Hello" is written as a function of n, let's set up the equation based on the given function:

Function F(n):

1. If n > 1, then

2. For i = 1 to n, Print "Hello"

3. For i = 1 to 10, F(n/3)

Now, let's analyze how many times "Hello" is printed at each level of recursion:

1. For the initial call, n is the input value.

2. The first loop (i = 1 to n) prints "Hello" n times.

3. The second loop (i = 1 to 10) calls the function F(n/3) ten times.

So, we can set up the equation as follows:

Total "Hello" prints = n + 10 * F(n/3)

Now, let's consider the recursive nature of the function. Each recursive call reduces the value of n to one-third of its previous value (n/3). The process continues until n becomes less than or equal to 1 (the base case).

If we solve the equation recursively, we get:

F(n) = n + 10 * F(n/3) F(n/3) = (n/3) + 10 * F(n/9) F(n/9) = (n/9) + 10 * F(n/27) ...

We can observe a pattern emerging in the recursive calls. Each time we reduce n by dividing it by 3, the coefficient in front of F(n/3^k) is (n/3^k).

Eventually, we reach a point where n/3^k is less than or equal to 1. Let's find the value of k when this happens:

n/3^k ≤ 1 n ≤ 3^k log base 3 (n) ≤ k

So, the recursive calls continue until k = log base 3 (n).

Now, let's sum up the terms:

Total "Hello" prints = n + 10 * F(n/3) + 10 * F(n/9) + ... + 10 * F(n/3^k)

Total "Hello" prints = n + 10 * (n/3) + 10 * (n/3^2) + ... + 10 * (n/3^k)

This is a geometric series with the first term (a) as n and the common ratio (r) as 1/3.

Total "Hello" prints = n * (1 + 1/3 + 1/3^2 + ... + 1/3^k)

The sum of an infinite geometric series is given by the formula:

Sum = a / (1 - r)

Total "Hello" prints = n / (1 - 1/3)

Total "Hello" prints = n / (2/3)

Total "Hello" prints = (3n) / 2

So, the number of times "Hello" is printed as a function of n is (3n) / 2.