Quantcast

A community for students. Sign up today!

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

Miyuki

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

    Timer.Start run task timer.Stop

  3. Miyuki
    • one year 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
    • one year 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
    • one year 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
    • one year 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

Ask a Question
Find more explanations on OpenStudy

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.