Question

In: Computer Science

This function uses a curious mix of iteration and recursion: function F(n) if n < 1...

This function uses a curious mix of iteration and recursion:

function F(n)
    if n < 1 
        return 1
    t <- 0
    for i <- 0 to n
        for j <- i to n
            t <- t + j
    return t + F(n-1) 
What is the number of basic operations (additions and subtractions) performed? Answer: Θ(n³)

Could you tell me how I can solve this problem??

Solutions

Expert Solution

This is a recursive function. so, follow these steps for calculating it's time complexity.

total amount of work done per one recursive call:
--------------------------------------------------
There are two for loops
outer for loop iterates n times
inner for loop iterates n times
so, total number of operations = n^2 = O(n^2)

size of the recursive call: n-1.  (because of F(n-1))
number of recursive calls inside F(n) = 1. (single recursive calls to F(n-1)

so, overall time complexity T(n) = 1*T(n-1) + O(n^2)
T(n) = T(n-1) + O(n^2)

let's solve this recurrence relation:
--------------------------------------
T(n)
= T(n-1) + n^2
= T(n-2) + (n-1)^2 + n^2
= T(n-3) + (n-2)^2 + (n-1)^2 + n^2
= T(1) + 2^2 + ... + (n-2)^2 + (n-1)^2 + n^2
= 1 + 2^2 + ... + (n-2)^2 + (n-1)^2 + n^2
formula for sum of squares of first n numbers is n(n+1)(2n+1)/6
ignore constance terms.
so, time complexity is O(n^3)

Answer: O(n^3)

Related Solutions

Describe the similarities between using recursion versus iteration. Describe the difference between using recursion versus iteration.
Describe the similarities between using recursion versus iteration. Describe the difference between using recursion versus iteration.
Let function F(n, m) outputs n if m = 0 and F(n, m − 1) +...
Let function F(n, m) outputs n if m = 0 and F(n, m − 1) + 1 otherwise. 1. Evaluate F(10, 6). 2. Write a recursion of the running time and solve it . 3. What does F(n, m) compute? Express it in terms of n and m.
#2 The Jacobsthal sequence is defined by J(1)=J(2)=1 and J(n)=J(n-1)+2J(n-2). Use recursion to write a function...
#2 The Jacobsthal sequence is defined by J(1)=J(2)=1 and J(n)=J(n-1)+2J(n-2). Use recursion to write a function that takes in a positive integer n and returns the nth Jacobsthal number. >>> J(8) 85 >>> J(9) 171 #3 Use recursion to write a function that takes in a positive integer n and returns all n digit numbers containing only odd digits. >>> f(1) [1, 3, 5, 7, 9] >>> f(2) [11, 13, 15, 17, 19, 31, 33, 35, 37, 39, 51, 53,...
Suppose f : N→N satisestherecurrencerelation f(n + 1) (f(n) 2 if f(n)iseven 3f(n)+ 1 if f(n)isodd...
Suppose f : N→N satisestherecurrencerelation f(n + 1) (f(n) 2 if f(n)iseven 3f(n)+ 1 if f(n)isodd . Notethatwiththeinitialcondition f(0) 1,thevaluesofthefunction are: f(1) 4, f(2) 2, f(3) 1, f(4) 4, and so on, the images cyclingthroughthosethreenumbers. Thus f isNOTinjective(andalso certainlynotsurjective). Mightitbeunderotherinitialconditions?3 (a) If f satisestheinitialcondition f(0) 5,is f injective? Explain whyorgiveaspecicexampleoftwoelementsfromthedomain withthesameimage. (b) If f satisestheinitialcondition f(0) 3,is f injective? Explain whyorgiveaspecicexampleoftwoelementsfromthedomain withthesameimage. (c) If f satisestheinitialcondition f(0) 27,thenitturnsoutthat f(105) 10 and no two numbers less than 105 have the same...
Fibonacci Sequence: F(0) = 1, F(1) = 2, F(n) = F(n − 1) + F(n −...
Fibonacci Sequence: F(0) = 1, F(1) = 2, F(n) = F(n − 1) + F(n − 2) for n ≥ 2 (a) Use strong induction to show that F(n) ≤ 2^n for all n ≥ 0. (b) The answer for (a) shows that F(n) is O(2^n). If we could also show that F(n) is Ω(2^n), that would mean that F(n) is Θ(2^n), and our order of growth would be F(n). This doesn’t turn out to be the case because F(n)...
T/F 1) The function f(x) = x1 − x2 + ... + (−1)n+1xn is a linear...
T/F 1) The function f(x) = x1 − x2 + ... + (−1)n+1xn is a linear function, where x = (x1,...,xn). 2) The function f(x1,x2,x3,x4) = (x2,x1,x4,x3) is linear. 3) For a given matrix A and vector b, equation Ax = b always has a solution if A is wide
Let f:(a, b) → R be a function and n∈N. Assume that f is n-times differentiable...
Let f:(a, b) → R be a function and n∈N. Assume that f is n-times differentiable and f^(n)(x) = 0 for all x∈(a,b). Show that f is a polynomial of degree at most n−1.
Define the following function f(n) = 5(2^n)-(2^(n-1)), n ≥ 1. Write a recursive definition for the...
Define the following function f(n) = 5(2^n)-(2^(n-1)), n ≥ 1. Write a recursive definition for the function f(n)? Consider the following recurrence: an= 2an-1 + 3 (where a1 = 1). Compute the values of an for n ≤ 5. Find a solution for the recurrence definition and validate its correctness. Consider the following recurrence: an=2an-1 +an-1an-2 (where a1 = 1). Compute the values of an for n ≤ 5.
Recursion and Iteration in C++ Locate the TODO comments in the hw02.h file. These comments provide...
Recursion and Iteration in C++ Locate the TODO comments in the hw02.h file. These comments provide direction on what needs to be done. // hw02.h #ifndef CSC232_HW02_H #define CSC232_HW02_H // TODO: All pre-conditions must be validated using the assert function imported from the following library. // TODO: You are not allowed to use the pow function in this assignment! #include <cassert> #ifndef FALSE #define FALSE 0 #endif #ifndef TRUE #define TRUE !FALSE #endif #define USE_MAIN_INPUT_FILE FALSE #define USE_DEMO_INPUT_FILE FALSE #define...
For f: N x N -> N defined by f(m,n) = 2m-1(2n-1) a) Prove: f is...
For f: N x N -> N defined by f(m,n) = 2m-1(2n-1) a) Prove: f is 1-to-1 b) Prove: f is onto c) Prove {1, 2} x N is countable
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT