Bubble Sort is known to be an O(N2)) algorithm. If a program using this sort completes in .001 seconds when N = 100, what will be the likely execution time in seconds when N equals each of the following values?
N = 1000
•N = 10,000
•N = 100,000
•N = 1,000,000

How do I figure this out?

Question

Bubble Sort is known to be an O(N2)) algorithm. If a program using this sort completes in .001 seconds when N = 100, what will be the likely execution time in seconds when N equals each of the following values? 
N = 1000
•N = 10,000
•N = 100,000
•N = 1,000,000

How do I figure this out?

anonymous · Answer

Yay, algorithmic analysis! I love this!
Since Bubble Sort is an $O(n^2$ algorithm, we know that its running time will be proportional to its input value. Thus, because when $N = 100$, the running time is .001, it must be that $T_r(n) = (\log n)^{-1}$. In other words, it completes in .01 seconds when N = 1000, so on.
I may have misread the question

anonymous · Answer

Okay how would you know to use log... and then why would you know to use that... I'm sorry im very confused when it comes to big oh notations

anonymous · Answer

It's actually just a very painful way of saying the zeros shift.
.001 is 10^(-3), and when N = 10^3, 10^(-3) is the running time.
.01 is 10^(-2) and when N = 10^4, 10^(-2) is the running time.
So on.

anonymous · Answer

Okay and the log equations is basically how it shifts... but how would one deduce that from the original problem.. how would I know to use log or even set my equation up that way... does log anything reduce numbers 10 fold?

anonymous · Answer

Well, log isn't commonly used when describing this sort of thing, but I certainly find it convenient. When I say log, I am referring to the common logarithm (log base 10). When we take log(100), it returns 2, because 10^2 = 100.

anonymous · Answer

okay thank you this helps a lot..  I wouldn't want to be a bother but do you mind explaining these terms O(f(N)), ƒÇ(f(N)), ƒÁ(h(N)) , and o(f(N))

anonymous · Answer

I can't see your post properly, OpenStudy's formatting is broken right now. However, I believe you are asking for explanations of theta, omega, big-oh, and little o notation?

anonymous · Answer

Yeah let me repost that

anonymous · Answer

ohh it still shows up the same

anonymous · Answer

Yes that's what im referring too

anonymous · Answer

I think that a few documents I watched a while back will help you more than I can. This guy at Berkeley is awesome. http://www.youtube.com/watch?v=VIS4YDpuP98

anonymous · Answer

Thanks!!