Question

1. Mathematically analyze the given Recurrence Relation and find out the time complexity of the algorithm.

T(n) = T(n-1)+1 , if n> 0 1 if n = 0

Answer 1

Mathematically:

• Recurrence: T(n) = T(n-1) + 1, here we take initial condition t(1) = 2
• Now going towards the problem:(Solving it)
  • T(1) = 2, Initial condition
  • T(2) = T(1) + 1 = 2+1 = 3
  • T(3) = T(2) + 1 = 3+1 = 4
  • T(4) = T(3) + 1 = 4+1 = 5
  • T(5) = T(4) + 1 = 5+1 = 6
• Initially what we had guessed
  • T(n) = n + 1
• 
  
• Checking informally so that are answer is mathematically correct:
  • T(n) = T(n-1)+1 = [(n-1)+1] + 1 = n+1
  • T(1) = 1+1 = 2
• 
  
• Therefore,mathematically proven.

Time complexity we have check by backward substitution:

Time complexity:

• Now we search for a pattern:
  • T(n) = T(n-1) + 1
  • T(n) = [T(n-2)+1] + 1
  • T(n) = [[T(n-3)+1]+1] + 1
  • T(n) = [[[T(n-4)+1]+1]+1] + 1
  • ...
  • T(n) = [...[[T(n-k)+1]+1] ... +1] + 1 [has k ones]
  • ... [Let k = n-1]
  • T(n) = [...[[T(n-(n-1))+1]+1] ... +1] + 1 [has k=n-1 ones]
  • T(n) = T(n-(n-1)) + (n - 1)
  • T(n) = T(1) + (n-1)
  • T(n) = 2 + (n - 1)
  • T(n) = n + 1
• Check the guess, by substituting, as in mathematically solved example
  • T(n) = T(n-1)+1 = [(n-1)+1] + 1 = n+1
  • T(1) = 1+1 = 2

Therefore time complexity:  T(n) = Θ(n)

Hope this may help you............Have a nice day ahead..........