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)

venereology answered 1 year ago

Next > < Previous

Related Solutions

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.

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...

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.

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

Subjects