How To Calculate Approximate Expectation Of Function Of A Binomial Random Variable?

Calculate function running time

• I have to make efiiciency check for diffrent traversal like preorder,inorder and postorder. I have make a switch case for user selection and difffrent proceducers for the traversal and these procedurers are recursive. My Problem is that when i calculate time in the procedure they calculate and print in vrious time i.e how many time it does recurstion. And i calculate it in switch case it gives start time and end time same can u help me out to solve this ?? I have to make efiiciency check for diffrent traversal like preorder,inorder and postorder. I have make a switch case for user selection and difffrent proceducers for the traversal and these procedurers are recursive. My Problem is that when i calculate time in the procedure they calculate and print in vrious time i.e how many time it does recurstion. And i calculate it in switch case it gives start time and end time same can u help me out to solve this ??

• Answer:

  I cannot answer this for sure as you fail to mention what you are using to obtain the times, nor the code in case you made a silly mistake. Note also that timing function execution times is a trickier business than you would think. First off you need to consider the characteristics of the start and end times you are obtaining: - what is the returned times' resolution? If the timed code takes less than the resolution of the time values to execute then the difference between end and start times will be zero. For example the C/C++ library time function returns an unsigned integer value that is typically the number of seconds elapsed since some starting point called the epoch. A modern computer can execute a heck of a lot of code in one second. The C/C++ library clock function returns a value with a resolution of CLOCKS_PER_TICK - which may have values of say 1000 (millisecond resolution) or 1000000 (microsecond resolution) or some other value, depending on the library implementation. Anther point here is that just because you have some supposed resolution, what is the effective useful resolution? If say the value returned by a clock library function implementation with a CLOCKS_PER_TICK value of 1000000 jumps by a minimum of 1000 each time then it effectively only has millisecond resolution and not the supposed microsecond resolution indicated by the CLOCKS_PER_TICK value. - what does the time measure? There are two main things a time function can measure - real elapsed time - ticks since machine or process or thread started, actual date and time - sometimes called wall clock time. Or it can measure time used by a process or thread - that is it does not count the time the process or thread is suspended for some reason - waiting for a signal or I/O or because some other thread or process was scheduled to execute. Note that different implementations of the clock C/C++ library function measure different things - for an example see the code and results at the end of an old AllExperts answer of mine at: http://en.allexperts.com/q/C-1040/time-milliseconds-Windows.htm Next we have to consider the sort of time your code would take to execute. Very often single executions of functions are short, especially for small data sets, and so may not take enough time to register for the effective resolution of your timing functions. Even if the calls do register a time then unless they are quite large values they are likely to fluctuate significantly if you are measuring elapsed, wall clock style times as such things as other threads executing will be counted, Even if you are measuring thread or process running time you will get variations due to issues such as memory access times differing due to differing states of system memory caches. To make function call times more significant repeat them - say 1000 or 1000000 or more times. If your functions' execution times depend on data set size then use a larger data set. However if you are testing various algorithms then maybe you need to use several data set sizes for each algorithm to see how they perform as data set size increases. You might like to vary the number of iterations for tests so that quick running small data set tests have a significant time and large data sets do not take too long to execute. You can of course calculate the time per iteration by dividing the duration for all iterations by the number of iterations. Be careful if you are using optimised code that the compiler does not remove any such loops entirely - this is probably less likely if you call a function in the loop as the compiler is less likely to know of any side effects the call may perform such as writing output or updating a global variable. To try and mitigate the effects of caching run the tests more than once and ignore the first (couple maybe?) set of figures. Finally collect many sets of timing data over many executions and average the results. Oh, here is a useful thread of discussion on nanosecond timing resolution: http://stackoverflow.com/questions/275004/c-timer-function-to-provide-time-in-nano-seconds If you need more serious code profiling then you should look at using profiling tools such as gprof (for GCC/ G++) or those that may be provided for your compiler or operating system (and possibly processor). http://en.wikipedia.org/wiki/List_of_performance_analysis_tools Hope you find this of use. Hello Hetal If you are using the Windows operating system, you can use the two calls to QueryPerformanceCounter to calculate the time a function call took. If you are using Linux, please let me know. The sample code below shows how to time a function call. For this test, the Sleep function is being timed. The code below compiles with Visual Studio. If you are using Turbo C++, you may need to change to and you may need to remove the line: using namespace std; I do not have Turbo C++, so I don't know what else would need to be done. The QueryPerformanceCounter returns the value of the CPU high-resolution counter. The functions below use that value, and the counter frequency to calculate elapsed time in milliseconds. If you don't care about milliseconds, but just want the elapsed time in counter ticks, then the code can be made even simpler. I hope that helps you out. Let me know if you have any other questions. typedef unsigned __int64 PC_t; PC_t PerfCounterFreq(void) { static PC_t result = 0; if (result == 0) { LARGE_INTEGER li; QueryPerformanceFrequency(&li); result = (PC_t)li.QuadPart; } return result; } PC_t PerfCounter(void) { LARGE_INTEGER result; QueryPerformanceCounter(&result); return (PC_t)result.QuadPart; } double ElapsedMs(PC_t start) { return double(PerfCounter() - start)/PerfCounterFreq()*1000.0; } using namespace std; int main(void) { PC_t start; double ms; start = PerfCounter(); Sleep(1000); ms = ElapsedMs(start); cout return 0; }