Question

How to figure out running time for each line of code when given a code (or pseducode)? I can't find any good YouTube video or good guide on it. For example, a question like this (not mine, just a random search result that I found): http://stackoverflow.com/questions/10497726/running-time-complexity-of-a-code-fragment

My task is to find out the running time of each line of code. I have my textbook but it isn't helping me :/ Please let me know if you have any good guide (whether video or webpage) so I can better understand the concept and calculate running time accurately. Thanks!

Answer 1

I guess you can run a timer... What are you coding in?

Answer 2

Timer.Start

run task

timer.Stop

Answer 3

@KonradZuse, sorry I meant on paper. It is for an algorithm course.

Answer 4

Most operations are finished in constant time, or O(1). The biggest exception are loops.

Suppose you have the following loop:

for( i = 0; i < n/2; i++ ) {
result *= i;
}

The body of the loop, `result *= i;` runs in O(1). The loop will iterator n/2 times. When combined, that makes this loop execute in O(1*n) = O(n) (linear time: take n twice as large and the execution time will also double).

A more complex example (borrowed from the link you gave):

for( i = 1; i < n; i *= 2 ) {
for( j = 0; j < n; j++ ) {
result *= i + j;
}
}

Like in the previous example, the loop that iterates over j is executed in O(n).
The outer loop will iterate over 1, 2, 4, 8, 16, and so on. So in total it will run log(n) times. (If n = 16, it will run log2(16) = 4 times). Each iteration of the outer loop requires O(n) time and the loop is run log(n) times, so the total time used for this code is O(n)*O(log(n)) = O(n*log(n)).

Final example:

for( i = 1; i < n; i *= 2 ) {
result *= i;
}
for( j = 1; j < n; j++ ) {
result += j;
}

Here we have one loop of O(log(n)) and one loop of O(n), one after the other. The total time would be O(log(n)) + O(n) = O(log(n) + n). Since the big O notation describes an upper bound, we only need the largest part, so we can simplify O(log(n) + n) to O(n).

I hope this answers your question.

Answer 5

@slotema THANK YOU SO MUCH!!! I usually don't type in all caps, but I really really appreciate your answer. It is super helpful!!!!! :D BIGGG INTERNET HUGS TO YOU!!!!

Answer 6

:) It was my pleasure.