Programmatically obtaining Big-O efficiency of code

by

It sounds like what you are asking for is an extention of the Halting Problem. I do not believe that such a thing is possible, even in theory.

Just answering the question “Will this line of code ever run?” would be very difficult if not impossible to do in the general case.

Edited to add:
Although the general case is intractable, see here for a partial solution: http://research.microsoft.com/apps/pubs/default.aspx?id=104919

Also, some have stated that doing the analysis by hand is the only option, but I don’t believe that is really the correct way of looking at it. An intractable problem is still intractable even when a human being is added to the system/machine. Upon further reflection, I suppose that a 99% solution may be doable, and might even work as well as or better than a human.

More Related Contents:

  1. Complexity of absolute difference and sum
  2. How to find nth prime with complexity o(1)
  3. What is a plain English explanation of “Big O” notation?
  4. Big O, how do you calculate/approximate it?
  5. How can I find the time complexity of an algorithm?
  6. Constant Amortized Time
  7. Is log(n!) = Θ(n·log(n))?
  8. How can building a heap be O(n) time complexity?
  9. How to find the lowest common ancestor of two nodes in any binary tree?
  10. What’s the fastest algorithm for sorting a linked list?
  11. What would cause an algorithm to have O(log log n) complexity?
  12. What is Constant Amortized Time?
  13. What is the best way to get the minimum or maximum value from an Array of numbers?
  14. Sorting in linear time? [closed]
  15. Big-oh vs big-theta [duplicate]
  16. Why do we ignore co-efficients in Big O notation?
  17. Time Complexity of two for loops [duplicate]
  18. Prove that binary heap build max comparsion is (2N-2)
  19. Explanation of Algorithm for finding articulation points or cut vertices of a graph
  20. Why is bubble sort O(n^2)?
  21. how to determine if the kth largest element of the heap is greater than x
  22. Do iterative and recursive versions of an algorithm have the same time complexity?
  23. Computational complexity of base conversion
  24. How to apply binary search O(log n) on a sorted linked list?
  25. Priority scoring algorithm [closed]
  26. Choosing n numbers with fixed sum
  27. What is a good Hash Function?
  28. Check if one integer is an integer power of another
  29. Random points inside a parallelogram
  30. Calculating frames per second in a game

Leave a Comment