Skip to content

Divide and Conquer

  • first you divide in subproblem
  • then you merge them

OR

  • you do some computation
  • then you crete two or more same subproblem to solve

Time Complexity

  • you have to make a recurrence relation for time complexity, and then solve it using Masters Theorem.

Merge Sort

  • split array into two
  • sort them recursively
  • merge them

quick sort

  • find pivot, and separate elements
  • sort the other parts recursively

Questions