Visual Studio time complexity

Discussion in 'Programmer's Corner' started by Dritech, Jan 12, 2015.

  1. Dritech

    Thread Starter Well-Known Member

    Sep 21, 2011
    756
    5
    Hi all,

    Is there a way for visual studio to show the time complexity (for the Big-O notation) of each line?

    I am determining the Big-O notation complexity of a loop, but for most line I don't know their actual complexity value.

    Examples are:
    Item tempItem = stkList;
    Console.ReadLine();
    Console.Clear();
    tax = ((taxRate / 100) * price) + price;

    How can I determine their equivalence complexity value please?
     
  2. kubeek

    AAC Fanatic!

    Sep 20, 2005
    4,670
    804
    I doubt that. You would have to analyze the program by yourself to find out. For example tax = ((taxRate / 100) * price) + price; is surely O(1)
     
    vpoko likes this.
  3. WBahn

    Moderator

    Mar 31, 2012
    17,716
    4,788
    Time complexity is an asymptotic description of how long a computation takes as the number of things, or the size of the set, being computed grows without bound. So when you have a loop that is, say, determining the tax charged for the sale of N items, what you want to do is first ask whether or not how long each pass through the loop takes is in anyway dependent on the number of items. Probably not. So this has O(1), namely it takes a constant amount of time independent of the number of items. Exactly how long it takes is immaterial because, in the limit that N goes to infinity, any process that has higher than constant complexity, say O(N), will eventually take longer than any O(1) process for some value of N (and greater).
     
  4. vpoko

    Member

    Jan 5, 2012
    258
    47
    The easiest way is to put a counter inside your innermost loop and check its value after the loops exit. Time complexity only makes sense if you're looping, iteratively or recursively. And like WBahn said, this won't tell you the actual asymptotic complexity since that would require running the loop forever and looking at the growth rate, but it will tell you the practical (finite) complexity of your loops.
     
Loading...