Reply to: Big O notation.

[DaveB]

In the proper FORTRAN notation...

If you can find it in amongst all the declarations and assorted bagage in your typical Fortran code

[SallyAnne]

because the product of two numbers is at most the square of the largest.

Ahhhhhh!!!!!!! I see!!!!!

The light goes on!!!!!

Owlhoot - you've always been my favourite

P.S. What does "get a word" mean?

"have a word with yourself"....meant lovingly, as your previous post had been so advanced it'd made my head actually explode.



many many thanks, and to everyone else too x x x

[NotAllThere]

You might see ^ written as ** , just to confuse matters.

[OwlHoot]

Thanks all of you.

Can I ask then....if you're multiplying 2 numbers...

why is it O(n^2) and not O(n*m)?

Does it not matter that the 2 numbers which we're multiplying are not the same? Does n simply mean "input"?

because the product of two numbers is at most the square of the largest. So as the O notation represents an upper bound you may as well use the square (that and the fact that you then express it in terms of one "variable").

BTW, you can multiply two numbers of size n (upper bound on both) in O(n.log(n)) by using a fast Fourier transform

P.S. What does "get a word" mean?

[TimberWolf]

what it's for, and why we would use it etc.

It makes it easy to spot in an instant how long a function or algorithm would take to run for a given size of input.

Like, what is ^ ?? I've never seen that symbol used before, so I dont get how it relates to the multiplication answer. I really dont understand O(n^2) at all

As others have said, ^ means raised to a power (exponentiation), it'll be a useful little button to find on your calculator Linear O(n^1) [the '1' being unnecessary], quadratic is O(n^2) etc. Quadratic functions quickly become slower to run than linear ones as the size of input grows, because the number of operations grows as the square of n. So if n were 10 say, a O(n) function would take 10 steps to complete, and a quadratic one 100.

[DaveB]

Thanks all of you.

Can I ask then....if you're multiplying 2 numbers...

why is it O(n^2) and not O(n*m)?

Does it not matter that the 2 numbers which we're multiplying are not the same? Does n simply mean "input"?

O(n^2) does not mean O(n*2) it means O(n to the power of 2). Now in this particular case n^2 = n*2, but n^4 <> n*4.

n^m is n to the power of m, not n*m.

If I understand it correctly you use different powers of n based on the format of the data you are using.

[EternalOptimist]

It's all about functions right?

So imagine you are at this do. It takes ten minutes to get to the bar and back forra round. So yous have to calcumerlate the optimum time taken for the dregs because yous dont want to be sitting there dry, do you?
If yous get to the bottom of the glass, it's 'oh ffs'. If everyone gets there is 'OH ffs' - thats the big O.

Next week - Algo-Rythm and Computational-Complexity(checking yer change)

[SallyAnne]

Thanks all of you.

Can I ask then....if you're multiplying 2 numbers...

why is it O(n^2) and not O(n*m)?

Does it not matter that the 2 numbers which we're multiplying are not the same? Does n simply mean "input"?

[d000hg]

An easy way to understand what O(n), O(n^2) mean is to imagine you are doing something with an array of n elements.

If you simply want to add all the values in an array, you need to look at each one once. If you double the number of elements you double the amount of items to look at.

If you want to sum elements in an NxN 2D array, you have to look at n^2 elements. If you double n, the number of elements is increased by 4.

It gets more complicated when we get into O(log(n)) but simple examples explain the point (I hope).

In designing an algorithm, knowing the what O it has is important... if you are testing on a small dataset of 100 elements, and then in real life run it on 10000 elements, O(n) will be 100 times slower... but O(n^2) will run 10,000 times slower.

[SallyAnne]

There's a Wikipedia article here.

Writing f(x) = O(log(x)) for example just means that for sufficiently large x, |f(x)| is less than C.log(x) for some constant C.

Likewise, if f(x) is a polynomial, say x^n + .. + x + 5 then f(x) = O(x^n), because for sufficiently large x the leading term (with the highest power) dominates all the others however large their coefficients, and this argument can easily be formalized:

|a_n.x^n + .. + a_1.x + a_0| <=

<= |a_n.x^n| + .. + |a_1.x| + |a_0|

<= |a.x^n| + .. + |a.x| + |a| where |a| = max(|a_i|)

= |a| . (|x^n| + .. + |x| + 1)

<= |a| . (|x^n| + .. + |x^n| + |x^n|)

= (n+1) . |a| . |x^n|

So the constant C can be taken as (n + 1).|a|

Have a word man!!!!!

[d000hg]

x^2 means x squared. It's used online a lot because superscript is a pain in the arse.

[DaveB]

Thanks Timber....

I have grasped the theory of it - what it's for, and why we would use it etc.

And I get that for all arithmetic operations, the size of the input will be the number of digits in the input numbers. That makes sense to me.

What I struggle with is the mathsy stuff.

Like, what is ^ ?? I've never seen that symbol used before, so I dont get how it relates to the multiplication answer.

I really dont understand O(n^2) at all


I will award you with one free "SallyAnne will concede in an argument" token if you can help me any further

IIRC the ^ operator is the text version of "to the power of" so 2^2 = 4, 2^3 = 8 etc cos you can't do it with the little number to the top right of the large one in text.

[suityou01]

Thanks Timber....

I have grasped the theory of it - what it's for, and why we would use it etc.

And I get that for all arithmetic operations, the size of the input will be the number of digits in the input numbers. That makes sense to me.

What I struggle with is the mathsy stuff.

Like, what is ^ ?? I've never seen that symbol used before, so I dont get how it relates to the multiplication answer.

I really dont understand O(n^2) at all


I will award you with one free "SallyAnne will concede in an argument" token if you can help me any further

^ means "to the power of".

For example

2^3 is 2 to the power of three, or 2*2*2

[SallyAnne]

Addition would be O(n) because the the problem only gets slower in direct proportion to the number of bits/bytes being added, and multiplication could be as high as O(n^2). The latter (quadratic time) not being too bad, at least compared to exponential functions, but not as fast as linear or constant time algorithms.

Thanks Timber....

I have grasped the theory of it - what it's for, and why we would use it etc.

And I get that for all arithmetic operations, the size of the input will be the number of digits in the input numbers. That makes sense to me.

What I struggle with is the mathsy stuff.

Like, what is ^ ?? I've never seen that symbol used before, so I dont get how it relates to the multiplication answer.

I really dont understand O(n^2) at all


I will award you with one free "SallyAnne will concede in an argument" token if you can help me any further

[OwlHoot]

There's a Wikipedia article here.

Writing f(x) = O(log(x)) for example just means that for sufficiently large x, |f(x)| is less than C.log(x) for some constant C.

Likewise, if f(x) is a polynomial, say x^n + .. + x + 5 then f(x) = O(x^n), because for sufficiently large x the leading term (with the highest power) dominates all the others however large their coefficients, and this argument can easily be formalized:

|a_n.x^n + .. + a_1.x + a_0| <=

<= |a_n.x^n| + .. + |a_1.x| + |a_0|

<= |a.x^n| + .. + |a.x| + |a| where |a| = max(|a_i|)

= |a| . (|x^n| + .. + |x| + 1)

<= |a| . (|x^n| + .. + |x^n| + |x^n|)

= (n+1) . |a| . |x^n|

So the constant C can be taken as (n + 1).|a|