## Miyuki 2 years ago 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!

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

3. Miyuki

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

4. slotema

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.

5. Miyuki

@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!!!!

6. slotema

:) It was my pleasure.