accurate running time of each line and total running time

Question

Show the accurate running time of each line and total running time for the following function:

int f1(int n, int A[ ], int B[ ])
{

            if ( (n>=5) || (n<0) )
                        return 0;

            for (int i=0; i<=n; ++i) 
                {
                    A[I] = 0;
                    for (int  j=0;  j<i;  ++j) 
                            B[I] = A[I] + I;
                }
            return 0;          
}

I do this:

4a (t(fetch)+t(cmp))   n>=5
4b (t(fetch)+t(cmp))            n < 0

6a (t(fetch)+t(store))      i = 0
6b (2t(fetch)+t(cmp)) * (n+1)   i<= n
6c (2t(fetch)+t(+) +t(store)) *n    ++i

8  (3t(fetch)+t([])+t(store))    A[I] = 0;

9a (t(fetch)+t(store))   j = 0
9b (3t(fetch)+t(cmp))   j < i
9c (2t(fetch)+t(+) +t(store)) *n  ++j

10 (7t(fetch)+2t([])+t(store)   B[I] = A[I] + I;

12 t(return)

23t(fetch)+4t(cmp)+6t(store)+2t(+)+3t([])*3n*(n+1)+t(return)

I do that right?

Answer 1

Sorry, but your question gives me a chuckle. (I suppose maybe it's a way to get you thinking about big-O issues.)

In any case, there's no harm in doing the kind of counting you are doing. (I'm not sure if you got the inner loop right.) It could make you think, and the most benefit could come when you realize it's not that simple.**

For example, if you look at actual assembly language, you may find it doing things you don't expect, such as calling functions for its own reasons.

If you really want to know total time and what percent of time each line (or instruction) is responsible for, I would recommend a profiler such as Zoom or LTProf. They are wall-time stack samplers that report the percent of samples each line appears on. That works even when there are function calls, recursion, I/O, you name it. (I do it manually.)

If you're really interested in this subject, consider these issues.

** Did a teacher assign this problem? If so, you might refer him/her to stackoverflow. There's a lot of expertise here.