In: Computer Science
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?? |
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)