0

I want to find out the time complexity of this function by using induction f(n) = 0, if n = 0

f(n) = f(n − 1) + 2n − 1, if n ≥ 1 Im using a method call repeated substitution so then i found a close form for f(n)

f(n)= f(n − 1) + 2n − 1 =f(n-2)+4n-4 =f(n-3)+6n-8 .... =f(n-i)+2^in-d

and then by taking i=n i came out with f(n)=f(0)+2^(n+1)-d and can conclude that is has a time complexity of O(2^n) since f(0) and d are all constants.

however i found the answer should be O(n^2) and where did i do wrong

ddd suman
  • 55
  • 1
  • 8

2 Answers2

1

Your math was wrong.

f(n) = f(n - 1) + 2n - 1
f(n) = f(n - 2) + 4n - 4
f(n) = f(n - 3) + 6n - 9
...
f(n) = f(n - i) + 2i n - i^2

When i = n you have:

f(n) = f(n - n) + 2n n - n^2
     = f(0) + (2 - 1) n^2
     = n^2

Therefore, f(n) is O(n^2)

However you are mistaken. This is not the time-complexity of the function, which is O(n) since that's how many recursions it has, this is the function's order, which means how "quickly it diverges". O(n^2) means the function diverges at a quadratic rate.

Patrick Roberts
  • 49,224
  • 10
  • 102
  • 153
  • thanks, i know where i did wrong but for the constant 1 ,4 ,8 it does not go up by i^2 the next term is actually 13,19,26 goes by 1+3,+4+5+6... i know this wouldn't matter with final answer but how could i prove that f(n+1) holds considering this – ddd suman Jul 12 '15 at 03:58
  • @dddsuman well that's certainly different than what you originally posted which was 1, 4, 9, ... – Patrick Roberts Jul 12 '15 at 06:18
  • @PatrickRoberts Hi..I am having one doubt to clear about your statement as **This is not the time-complexity of the function, which is O(n) since that's how many recursions it has, this is the function's order, which means how "quickly it diverges**. while reading another post [link](http://stackoverflow.com/questions/13467674/determining-complexity-for-recursive-functions-big-o-notation#) In the mentioned link it says that the time complexity are "n^2" or "n" etc. Can you please clear how to find time complexity for recursive then? Thanks in advance :) – pulse Oct 04 '15 at 22:11
  • That's because each recursive call in that link has a time complexity dependent on n. Since this function is only a direct recursive call to itself, each function call is O(1) but since the amount of recursions is equal to n, the time complexity for the function is O(n). – Patrick Roberts Oct 04 '15 at 22:17
0

I don't fully understand the question. The complexity of calculating the value is O(n), because you can just do the calculation starting from 0:

f(0) = 0
f(1) = 0 + 2*1 - 1 = 1
f(2) = 1 + 2*2 - 1 = 4
f(3) = 4 + 2*3 - 1 = 9

Actually, you probably get the idea . . . the nth value is n^2. I am guessing in the context of the problem that this is what they want the answer to be. However, to calculate it seems to be O(n).

Gordon Linoff
  • 1,242,037
  • 58
  • 646
  • 786