Big O notation

[yancho]

Guys,

I have finished this query,

SELECT DISTINCT ON (c1)
c1.city_name AS "c1",
c2.city_name AS "c2",
distance(c1.the_geom, c2.the_geom),
makeline(c1.the_geom, c2.the_geom)
FROM
city c1
JOIN
city c2
ON (
c1.city_name <> c2.city_name
)
ORDER BY c1, distance ASC
;



On a table with 16 rows, and was told that my execution time increases to O(n^2).

First of all, having 28000 rows, do you agree that it will increase at that range?

I tried to understand the Big O notation from wikipedia but went in too much maths, and its really not my forte, so can you guys please explain this notation in more easier words please?

Cheers

[Stewwi]

Big O Notation is a formula that represents how long an algorithm takes to execute. So if the algo dosent change the formula will stay the same.

The rows are represent the value n, so as such it changes the value if you decide to work it out..

Hope that helps

[yancho]

but what O signifies? seconds? what?

I mean atm it is O(16^2) = 256 .. pero for sure it didnt remain 256 seconds

and we are saying that it will be O(28000^2) = 784000000 .. but be what? seconds / split seconds what?

[Stewwi]

O varies a lot, depends on the CPU. Generally the big O notation isnt used to give a numerical value to an algorithm. It is used to compare one with another.

Tipo If I have two algos that do the same thing and one takes O(n) to execute and the other O(n^2) I know that the first one is much more effecient. O notation can be used to measure time and space (memory it need to execute)

[yancho]

so on the same PC O is a constant? (in the ideal word where there are no other software in memory .. ceteris paribus) ?

and to see how much time will it make is there some translation I can do? or i need to find how much it takes to execute this query and then square it?

[MaL^D^MaN]

O isnt really a function its just a way of seeing how an algorithm will perform when the load it has to do grows

the best O time wise would be n.

eg.
for(int i = 0; i < 10;i++)
{
}

O(n)
--------------------------------
for(int i = 0; i < 10;i++)
{
for(int j= 0; j< 10;j++)
{
}
}

O(n)
--------------------------------

the O notation just shows u what to expect the performance of the algorithm to be. you have the best computer in the world but if ure algorithm has a O( n to the power of n) its not going to make much of a difference.

http://en.wikipedia.org/wiki/Big_O_notation#Common_orders_of_functions

check this table out. usually anything above polynomial is considered fine. obivously O(n) is ure best bet.

eg. algorithm which was given 1000 items to process an algorithm with O(n) would take 1000seconds for example but if the algorithm is O(n!) u have 1000! seconds which would mean u have to wait for example a couple of years. it doesnt actually show u how long in seconds ure algorithm would take but it just shows u the scalabilty of ure algorithm.

[yancho]

cheers xbin .. thanks :)

[GeneralOneBall]

Originally posted by MaL^D^MaN
O isnt really a function its just a way of seeing how an algorithm will perform when the load it has to do grows

the best O time wise would be n.

eg.
for(int i = 0; i < 10;i++)
{
}

O(n)
--------------------------------
for(int i = 0; i < 10;i++)
{
for(int j= 0; j< 10;j++)
{
}
}

O(n)
--------------------------------

the O notation just shows u what to expect the performance of the algorithm to be. you have the best computer in the world but if ure algorithm has a O( n to the power of n) its not going to make much of a difference.

http://en.wikipedia.org/wiki/Big_O_notation#Common_orders_of_functions

check this table out. usually anything above polynomial is considered fine. obivously O(n) is ure best bet.

eg. algorithm which was given 1000 items to process an algorithm with O(n) would take 1000seconds for example but if the algorithm is O(n!) u have 1000! seconds which would mean u have to wait for example a couple of years. it doesnt actually show u how long in seconds ure algorithm would take but it just shows u the scalabilty of ure algorithm.

abela couldn't have said it any better! :p

[MaL^D^MaN]

Originally posted by GeneralOneBall
abela couldn't have said it any better! :p

abela taught it to me hehe