0

First of all I know this is not a direct coding question, but please don't close it as I badly need suggestions on this.

I would like to understand and get a good grasp of the time complexity fundamentals to figure out the complexity of the programs I write or for any given program. I went through the time complexity stuff in "Introduction to Algorithms" book by Thomas H. Cormen. After that I am easily able to figure out if a program has a complexity of O(n) or O(n^2), but I face difficulty when it comes to log(n) and other.

What is the best way to master on the time complexity fundamentals so I could correctly figure out complexity of any given algorithm? Please provide some suggestions on books or videos that could help me understand it.

tech_human
  • 6,592
  • 16
  • 65
  • 107
  • You question goes wrong when you ask what the "best" way is, and then again when you ask for suggested texts etc. You *could* improve it by giving an example of a lg n example and state where you misunderstand probably. – ChiefTwoPencils Oct 16 '14 at 01:14
  • Do you have a good understanding of the mathematical basis for the log function? If not, start there. If you do, then using heap sort as the example, exactly which part of the analysis in deriving the `O(nlogn)` time complexity do you find difficult to understand? I think the first step to understanding something is to first figure out exactly what it is that you do not understand. Your question as it stands is simply too broad and can be summarized as "Teach me log usage in time complexities please." Finally, try asking in http://cs.stackexchange.com/. – wookie919 Oct 16 '14 at 01:35
  • +1 for understanding the math behind the log function. Most algorithms covered in textbook are logarithm to the base 2. Try understanding what the base 2 means and what is the difference between log base 2, 3,10 etc. Check out the merge sort algorithm taught by Prof. Tim Roughgarden in this algorithms course - https://www.coursera.org/course/algo. The complexity analysis done there using the tree model will give you a good picture. Finally, try implementing algorithms such as binary search, merge sort, quick sort. You'll surely start developing an intuitive understanding of log complexity. – govin Oct 16 '14 at 06:59
  • I think you guys are right. I should revise my log knowledge first and then will checkout the links you all posted. This would help. Thanks! – tech_human Oct 17 '14 at 13:38

0 Answers0