News for hackers. Stuff that matters.
Re:Big-O notation explained by a self-taught programmer by YZF on Friday July 26, 2013 @08:41PM (#6111364)
Can you be more specific? :-)

You kind of need to know what a function is. That's not hard to explain either. Let's say we have f(x) = y. If I already lost you here let me know.

We say f is of O(N) (and this is a notation, not a function) if there exists two numbers, n1 and c such that for every n>n1 f(x)<cx. An example:

f(x) = 5 x

I can pick c = 6, n1 = 1, it's clear that for every value > 1 6x > 5 x. I just proved this function is O(N).

Note that f(x) = 1,000,000 + 5*x is also O(N), I just need to pick a large enough c and n1.

f(x) = x^2

There no c and n1 that will make the statement above true. f is not O(N).

There are no comments on this comment yet.