Big O

An algorithm that is O(lg n) takes 10 seconds to execute on a particular machine when n=10, how long should it take when n=80?

An algorithm that is O(n) takes 10 seconds to execute on a particular machine when n=100, how long should it take when n=500?

An algorithm that is O(n^2) takes 10 seconds to execute on a particular machine when n=500, how long should it take when n=500?


Jeez, how do i figure out this big o stuff? this stuff is confusing.

Comments

  • No it really isn't - it's actually a simplification of the time complexity of an algorithm. The Big-Oh notation specifes an upper bound to the time complexity; so it should not exceed that (worst case). The expression within the brackets is likely to be parametrized; it mostly depends on n. Mostly n is an indication of the amount of input.

    So say for example we're discussing a sorting algorithm. Since there are numerous algorithms with varying applications, they vary in time complexity. You could say one algorithm runs in O(n) time and another one in O(n^2) time. This means that, given n number to sort the first one sorts this in a time linearily proportional to that number. The second one sorts n numbers in time quadratically proportional to that number.

Sign In or Register to comment.

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

In this Discussion