Quantcast

Got Homework?

Connect with other students for help. It's a free community.

  • across
    MIT Grad Student
    Online now
  • laura*
    Helped 1,000 students
    Online now
  • Hero
    College Math Guru
    Online now

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

Miyuki

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!

  • one year ago
  • one year ago

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

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

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

    Timer.Start run task timer.Stop

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

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

    • one year ago
  4. slotema
    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.

    • one year ago
  5. Miyuki
    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!!!!

    • one year ago
  6. slotema
    Best Response
    You've already chosen the best response.
    Medals 2

    :) It was my pleasure.

    • one year ago
    • Attachments:

See more questions >>>

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.