how to write a recurrence relation for a given piece of code

Okay, so in algorithm analysis, a recurrence relation is a function relating the amount of work needed to solve a problem of size n to that needed to solve smaller problems (this is closely related to its meaning in math).

For example, consider a Fibonacci function below:

Fib(a) 
{
  if(a==1 || a==0)
    return 1;
  return Fib(a-1) + Fib(a-2);
}

This does three operations (comparison, comparison, addition), and also calls itself recursively. So the recurrence relation is T(n) = 3 + T(n-1) + T(n-2). To solve this, you would use the iterative method: start expanding the terms until you find the pattern. For this example, you would expand T(n-1) to get T(n) = 6 + 2*T(n-2) + T(n-3). Then expand T(n-2) to get T(n) = 12 + 3*T(n-3) + 2*T(n-4). One more time, expand T(n-3) to get T(n) = 21 + 5*T(n-4) + 3*T(n-5). Notice that the coefficient of the first T term is following the Fibonacci numbers, and the constant term is the sum of them times three: looking it up, that is 3*(Fib(n+2)-1). More importantly, we notice that the sequence increases exponentially; that is, the complexity of the algorithm is O(2n).

Then consider this function for merge sort:

Merge(ary)
{
  ary_start = Merge(ary[0:n/2]);
  ary_end = Merge(ary[n/2:n]);

  return MergeArrays(ary_start, ary_end);
}

This function calls itself on half the input twice, then merges the two halves (using O(n) work). That is, T(n) = T(n/2) + T(n/2) + O(n). To solve recurrence relations of this type, you should use the Master Theorem. By this theorem, this expands to T(n) = O(n log n).

Finally, consider this function to calculate Fibonacci:

Fib2(n)
{
  two = one = 1;
  for(i from 2 to n)
  {
    temp = two + one;
    one = two;
    two = temp;
  }
  return two;
}

This function calls itself no times, and it iterates O(n) times. Therefore, its recurrence relation is T(n) = O(n). This is the case you asked about. It is a special case of recurrence relations with no recurrence; therefore, it is very easy to solve.

Related Posts:

  1. How to solve: T(n) = T(n/2) + T(n/4) + T(n/8) + (n)
  2. In a triangulated isometric grid, what triangle is a given point in?
  3. What is a loop invariant?
  4. What is a loop invariant?
  5. What does O(log n) mean exactly?
  6. how to calculate binary search complexity
  7. When is it practical to use Depth-First Search (DFS) vs Breadth-First Search (BFS)? [closed]
  8. What does O(log n) mean exactly?
  9. What is Sliding Window Algorithm? Examples?
  10. Quicksort with Python
  11. What is the difference between tree depth and height?
  12. how to implement quick sort algorithm in C++
  13. Python: maximum recursion depth exceeded while calling a Python object
  14. Why is the time complexity of both DFS and BFS O( V + E )
  15. Time complexity of a Priority Queue in C++
  16. What is stability in sorting algorithms and why is it important?
  17. Breadth First Search time complexity analysis
  18. Counting the sum of every nodes’ neighbors’ degrees?
  19. Time Complexity of the Kruskal Algorithm?
  20. Quick Sort Vs Merge Sort
  21. Polynomial time and exponential time
  22. Insertion Sort vs. Selection Sort
  23. Difference and advantages between dijkstra & A star
  24. Best Case for Bubble Sort
  25. How to find the kth smallest element in the union of two sorted arrays?
  26. Big O, how do you calculate/approximate it?
  27. Performing Breadth First Search recursively
  28. Is Quicksort in-place or not?
  29. longest increasing subsequence(O(nlogn))
  30. O(n log n) vs O(n) — practical differences in time complexity
  31. When should I use Kruskal as opposed to Prim (and vice versa)?
  32. Trying to understand max heapify
  33. Shortest possible depth of a leaf in decision tree (comparison sorting algorithm)
  34. Python Weighted Random [duplicate]
  35. What is the meaning of “exclusive” and “inclusive” when describing number ranges?
  36. What’s a good algorithm to generate a maze?
  37. Intuition for perceptron weight update rule
  38. Easy: Solve T(n)=T(n-1)+n by Iteration Method
  39. What is tail call optimization?
  40. PacMan: what kinds of heuristics are mainly used?
  41. Quicksort vs heapsort
  42. Big-oh vs big-theta
  43. Best case time complexity for selection sort
  44. Looking for algorithm finding euler path
  45. Trie complexity and searching
  46. What does this definition of contiguous subsequences mean?
  47. Is log(n!) = Θ(n·log(n))?
  48. Is complexity O(log(n)) equivalent to O(sqrt(n))?
  49. How to find maximum spanning tree?
  50. Exactly how many comparisons does merge sort make?
  51. Algorithm to return all combinations of k elements from n
  52. How to calculate big-theta
  53. What is the time complexity of while loops?
  54. Merge sort time and space complexity
  55. Intuitive explanation for why QuickSort is n log n?
  56. Calculate distance between two latitude-longitude points? (Haversine formula)
  57. Shuffle a deck of cards in Java
  58. How to calculate time complexity of backtracking algorithm?
  59. Median of Medians in Java
  60. What is a loop invariant?
  61. Hash table runtime complexity (insert, search and delete)
  62. Which is better: O(n log n) or O(n^2)
  63. What is O(log* N)?
  64. Quickselect time complexity explained
  65. What is the proper equivalent of “while(true)” in plain C?
  66. Bellman-Ford vs Dijkstra: Under what circumstances is Bellman-Ford better?
  67. Asymptotic Notation – does n (log n) (log n) simplify?
  68. Difference between Big-O and Little-O Notation
  69. What is the big-O of the function (log n)^k
  70. How to calculate an angle from three points?
  71. Why is O(n) better than O( nlog(n) )?
  72. Is there an O(n) integer sorting algorithm?
  73. An example of Best Case Scenario for Quick Sort (Need someone to check if my answer is correct)
  74. Why is merge sort worst case run time O (n log n)?
  75. Why is merge sort worst case run time O (n log n)?
  76. What is the time and space complexity of a breadth first and depth first tree traversal?
  77. Create your own MD5 collisions
  78. Image Segmentation using Mean Shift explained
  79. Finding the median of an unsorted array
  80. Difference between Big-Theta and Big O notation in simple language
  81. What is the difference between bucket sort and radix sort?
  82. How are the following functions O(N^3)?
  83. Difference between O(n) and O(log(n)) – which is better and what exactly is O(log(n))?
  84. Finding all possible combinations of numbers to reach a given sum
  85. Are there any real O(n^n) algorithms?
  86. Sorting an array in C?
  87. Is Dijkstra’s algorithm for directed or undirected graphs?
  88. How to determine if a point is in a 2D triangle?
  89. Modular multiplicative inverse function in Python
  90. Minesweeper solving algorithm
  91. About bubble sort vs merge sort
  92. How do I check if an array includes a value in JavaScript?
  93. Kadane’s algorithm explained
  94. How to generate all permutations of a list?
  95. Is it more efficient to copy a vector by reserving and copying, or by creating and swapping? [duplicate]
  96. Why does cache use Most Recently Used (MRU) algorithm as evict policy?
  97. When will the worst case of Merge Sort occur?
  98. Finding the max/min value in an array of primitives using Java
  99. Which algorithm is faster O(N) or O(2N)?
  100. Best way to randomize an array with .NET

Leave a Comment