Got Homework?
Connect with other students for help. It's a free community.
Here's the question you clicked on:
 0 viewing
Miyuki
Group Title
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/runningtimecomplexityofacodefragment
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
Miyuki Group Title
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/runningtimecomplexityofacodefragment 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

KonradZuse Group TitleBest ResponseYou've already chosen the best response.0
I guess you can run a timer... What are you coding in?
 one year ago

KonradZuse Group TitleBest ResponseYou've already chosen the best response.0
Timer.Start run task timer.Stop
 one year ago

Miyuki Group TitleBest ResponseYou've already chosen the best response.0
@KonradZuse, sorry I meant on paper. It is for an algorithm course.
 one year ago

slotema Group TitleBest ResponseYou've already chosen the best response.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

Miyuki Group TitleBest ResponseYou've already chosen the best response.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

slotema Group TitleBest ResponseYou've already chosen the best response.2
:) It was my pleasure.
 one year ago
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
 Engagement 19 Mad Hatter
 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.