Member Avatar for aakk

I want more information about related to find complexity of algorithm.
For e.g. to find time complexity of quick sort by using recurrence relation.

  • 2 Contributors
  • 1 Reply
  • 46 Views
  • 12 Hours Discussion Span
  • Latest Post Latest Post by AuburnMathTutor
Member Avatar for AuburnMathTutor

A pretty sweet method is the Master Method (or the Master Theorem). Given a recurrence relation in a particular common form, it can often tell you immediately what the time complexity will be.

Otherwise, the general method to prove a time complexity from a recurrence is going to be to find an answer and then prove it using mathematical induction. As to how you find an answer... well, you can use techniques similar to those employed in proving the convergence of sequences.

In general, I believe solving generic recurrence relations is pretty tough. I might be mistaken, though.

You might be able to argue using a sort of tree. I know that is typically done for MergeSort, for instance.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.