1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

To empirically estimate the big-Oh in small programs

  1. Dec 16, 2014 #1
    1. The problem statement, all variables and given/known data
    First, I am a teacher preparing to give a discrete mathematics course, in which I will not do any computing, but the students will (in Python). I want them to make empirical estimates for the growth of their (short) recursive programs by putting in some sort of "counter" in their programs, and then run it on several sets of data of varying sizes. (I will also ask them to analyze theoretically, but that is not my question here.) But since I am not a programmer, I am not sure how to do this.

    2. Relevant equations
    N/A

    3. The attempt at a solution
    Simply have the program count the number of operations seems to me to be incorrect, because different operations will take different amounts of time and/or memory space. I am also aware that different machines (not to mention different versions of Python) will give different answers, but they should be within a linear factor of one another. Reading off the time for the completion of the program is not going to work, because the programs will be short. Some websites classify some operations complexity, but not all of them, and besides, that brings us back to a theoretical approach. Anyway, I don't want to actually give them the Python program construction (my students can program; I can't), but I will be suggesting the mathematical steps to put in. (Therefore an answer in mathematical language rather than computer language would be appreciated. I think the first mathematician to have seen a computer program reading "n=n+1" probably had a heart attack.)
    Thanks for any hints.
     
  2. jcsd
  3. Dec 16, 2014 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    You can always make the input longer (or let the programs run multiple times).
    Most of the time you have some set of loops with just one or two different operations executed many times. If they do not get called the same amount of times, you can count both separately. Or add them. If one is just a factor of 2-3 slower than the other, it does not matter much compared to a different complexity.
    I don't think it is a good idea to give students tasks you cannot solve.
     
  4. Dec 16, 2014 #3

    jedishrfu

    Staff: Mentor

    you can also query for millisecs and and do stats on the deltas :

    Code (Text):

    import time

    def do_something_here():
      print "hello world"

    # init timer
    oldticks=time.clock()

    # loop with timing
    for i in range(1000):

      do_something_here()

      newticks=time.clock()
      delta=(newticks-oldticks)
      oldticks=newticks

      print "loop: ",i,"  delta: ",delta, " secs"

     
     
  5. Dec 16, 2014 #4

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Printing can take some time on its own, so better do it outside the areas where time is evaluated.
     
  6. Dec 16, 2014 #5
    Thanks, mfb and jedishrfu. I guess combining the answers, having the students run the program lots of times, subtracting the time taken to record the result from each run, and then doing stats on the results, should do it.
    I do agree that giving students stuff that the instructor cannot solve is not a great idea; however, in this course, the computing part is relegated to a colleague with whom I split the course (I just do the maths part). That is, I know that the assignments I give are mathematically possible, but I need to give assignments that I know are computable in Python, even though my colleague will help them through the details. Therefore I am informing myself via this magnificent forum.
     
  7. Dec 17, 2014 #6

    jedishrfu

    Staff: Mentor

    Since, you're doing python and math together you both might want to check out Pyzo at pyzo.org. Its a collection of python libs + an interactive display where the environment is setup and ready to go. They don't have any example code but searching the web should find examples of how to use the various libraries available namely numpy, scipy, matplotlib ...
     
  8. Dec 17, 2014 #7
    Thanks, jedishrfu. The site looks very useful. In fact, the SymPy fits my idea what a computer should do. I shall recommend this to my students and to my colleague.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: To empirically estimate the big-Oh in small programs
  1. Big Oh notation (Replies: 2)

  2. Big-Oh Notation (Replies: 1)

Loading...