Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

Miyuki

  • 3 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!

  • This Question is Closed
  1. KonradZuse
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  2. KonradZuse
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Timer.Start run task timer.Stop

  3. Miyuki
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  4. slotema
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    @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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    :) It was my pleasure.

  7. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy