About complexity

rolfl

Aug 26, 2014 00:01

@TopinFrassi - Complexity is all about scaling, that's all you have to know.

If you double the data, what happens to the runtime.

TopinFrassi

It... doubles?

rolfl

if the runtime doubles when you double the data, then it is O(n).

Simon André Forsberg

@TopinFrassi The same amount of computer power is needed if you loop once but do two things in the loop, or if you loop twice and do one thing in each loop. You're still doing the same amount of things

Mat's Mug

(yay, I got that one right!)

rolfl

So, 'Big-O' notation is only about scalability, not about performance.

rather, it is how the performance is affected by scale.

not about how fast something goes at the current scale.

TopinFrassi

Aug 26, 2014 00:06

Can I ask another question?

rolfl

No .... ;-) Of course you can ... ;-)

I just have parents, work, chat, mod stuff, cat, and kids on the go here.

TopinFrassi

Thanks! So, when we talk about O(n^2), I thought it meant "Each time you go through an element of the collection, you go through all the collection again" or something like that, which seems to make sense. I fail to understand how is this different from going through the list twice or something like that. Why does O(n^2) affect scaling and not O(2n) (which is invalid, from what I now understand)

Well you can also answer whenever you have time, I don't have a gun against my head asking me to explain Big-O notation :P

Captain Obvious

0

Q: Winforms Dice Control

This is my second Custom Control I have made, a dice. The code below has worked 100% in all my tests, program contains 1 dice control and seven buttons, 6 for setting a number directly, and one for randomizing it. Feedback and improvement suggestions are greatly appreciated. using System; using ...

c# winforms

Simon André Forsberg

@TopinFrassi Let's say that you have a nested for loop. A for-loop inside a for-loop. And you're looping through the same list in both loops. Let's say that the list is 10 items, how is performance affected if you make the items to 20 instead?

@TopinFrassi Hint: Let's say that inside the inner for-loop you're printing "Hello World" to System.out, how many times will it be printed if the list is 10 items, and how many times will it print if the list is 20 items?

TopinFrassi

If the item has 10 elements it'll be printed 100 times, and 20 : 400. But what I don't understand is, if I have two loops that aren't nested, I would print Hello World 20 times with 10 elements, not 10..

So, "O(2n)". (I'm not trying to prove a point or anything, just trying to understand!)

Simon André Forsberg

Aug 26, 2014 00:22

@TopinFrassi Exactly. Now imagine if it would take one second to print something to System.out. If you have O(n^2) complexity, it would take 400 seconds instead of 100 seconds. If you have what we can call O(2n) complexity, it would take 40 seconds instead of 20 seconds.

So you see, if you increase the size of the list for O(n^2), the performance is affected much more than if you have O(2n)

TopinFrassi

Yes, so why isn't O(2n) considered, 40 seconds instead of 20 is still important, but much less than O(n^2)

So, we don't use O(2n) because the performance hit isn't big enough to be considered?

Simon André Forsberg

@TopinFrassi O(n) would be 20 seconds instead of 10 seconds. Which indicates a doubling. O(2n) is 40 seconds instead of 20 seconds, which is also a doubling. So technically, they have the same scaling.

Double the size, double the time required.

vs. O(n^2), where you double the size and get a quadratic increase in time required

TopinFrassi

oh I think it just flashed in my head

Saying that going through the array twice (O(2n)) is exactly the same as saying "If I go through the array one, the complexity is O(n) since they scale at the same rythm. O(n^2) is important because the time required is exponential comparing to the number of elements

Oops I realise I'm not clear. I mean, if I go through the array twice the performance will double, so the scaling of the algorithm stays O(n) since the performance scales the same way the data does. Where as O(n^2), the performance doesn't scale with the data, which is why it is specified O(n^2). Did I understand?

rolfl

Aug 26, 2014 00:38

Yes

And pleased I could help.

mjolka

@TopinFrassi have you looked at the formal definition? en.wikipedia.org/wiki/Big_O_notation#Formal_definition

rolfl

So, let's look at a typical real world situation

Someone writes the code: lineSize()

Simon André Forsberg

@TopinFrassi Not exponential, but polynomial. O(n^2) is veeeeery different from O(2^n)

TopinFrassi

@mjolka, I must say all these numbers made it pretty hard to understand!

By numbers I mean, anything but numbers ahah, all these variables*

rolfl

public int lineSize(String line) {
    char[] chars = line.toCharArray();
    int size = 0;
    for (int i = 0; i < chars.length; i++) {
        size++;
    }
    return size;
}

Now, that function returns the length of a string.

TopinFrassi

Aug 26, 2014 00:41

Yep

rolfl

Not very efficient.

You put that in a loop, and you have:

TopinFrassi

O(n^2)

no wait ehm

rolfl

for (String line : lines) {
    size += lineSize(line);
}

Now, you have two components, one is the size of the lines array/list, the other is the average length of each line.

RubberDuck

@Mat'sMug I admittedly don't see the benefit of using interfaces in VBA, so I may not be the best to ask. I think they're far too constricting.

rolfl

O(n x m) where n is the size of the list, and m is the average line length.

TopinFrassi

Aug 26, 2014 00:43

I understand that

rolfl

OK, so assume that the average line length never changes..... it is constant.

now, as you scale, the only thing that can scale, is n, or the number of items in the list.

RubberDuck

Unless you create a static helper function that takes an IPresenter by Ref.

rolfl

So, your time complexity is O(n).

TopinFrassi

Yep

rolfl

double the list size, and you double the time taken to compute.

So, someone says, hey, I have an O(n) method for calculating the size, and I say, yeah, but the base algorithm is really, really slow.

You have to look at both components.....

A loop that is written:

for (String line : lines) {
    size += line.length();
}

is far, far faster, and is also O(n).

TopinFrassi

Aug 26, 2014 00:46

Assuming Length() doesn't run through each character of the string to find the length

Right?

rolfl

exactly..... and, you will notice that the original loop uses data.length anyway.

it did not need to loop through the array to get the size of the array.

RubberDuck

And I've just learned a ton about Big O notation, so I'm glad you're in here asking about it @Topini.

TopinFrassi

I'm glad I did too, I thought I understood but I really didn't!

rolfl

Bottom line is that performance often relates to two things..... scale, and static.

sometimes, an O(2^n) operation is better than an O(1) operation, when n is small.

you have to be careful when you deal with these things.

There are some common things to be aware of.

TopinFrassi

a second, O(2^n) or O(n^2)?

rolfl

Aug 26, 2014 00:49

2^n is very bad.

n^2 is just pretty bad.

n^2 means that when you double the scale, you quardule the output.

2^n, for every element you add, you double the output time

TopinFrassi

That is terrible. Do you have an example of such an algo?

rolfl

actually, now I am thinking......

RubberDuck

Ummm wouldn't 2^n scale exponentially?

2n would double for every element.

mjolka

@TopinFrassi en.wikipedia.org/wiki/…

RubberDuck

2^1 = 2; 2^2=4; 2^3=8; 2^4=16

Ok, bad example. 2^n = 2n

No. No. I was right the first time.

rolfl

Aug 26, 2014 00:53

Travelling salesman problem too: en.wikipedia.org/wiki/…

TopinFrassi

I heard about that one

rolfl

An important one that comes up often is O(log n).

RubberDuck

NP problem... Bad juju.

rolfl

A binary search is log n

mjolka

@TopinFrassi here's a good exercise. using the formal definition i linked to before, prove that f(x) = 2x + 2 is O(x)

rolfl

Aug 26, 2014 00:55

each time through the loop, you eliminate half the data.

Which means, each time you doule the data, you only add one loop iteration.

TopinFrassi

I'll try it @mjolka!

rolfl

In essense, what this means, is that, for anything after about 32 elements, the binary search is O(1).

mjolka

:)

TopinFrassi

The binary tree (a balance one), is O(logN), right?

oops

rolfl

yes... and, think about it, if you double the tree, you only have one new level in it.

TopinFrassi

Aug 26, 2014 00:57

You were faster than me to write it!

rolfl

so, going from 1 element, to 2, the time doubles. then, to 4, it doubles again, and 8, 16, and 32.

TopinFrassi

Yes, wow I don't regret spending time here tonight instead of playing diablo 3.. :P

rolfl

So, 5 iterations for 32 members.

6 iterations for 64, which is only 20% slower, and 7 iterations for 128.

TopinFrassi

There's something I'm not sure I understood

@rolfl Why is it O(1)?

rolfl

at that point, the marginal increase for doubling the data is, in % terms, less than 5% and is probably not worth worrying about.

TopinFrassi

Aug 26, 2014 00:59

oops, wanted to link the message..

rolfl

@TopinFrassi Look at this article:

Logarithmic scale

A logarithmic scale is a nonlinear scale used when there is a large range of quantities. Common uses include the richter scale for earthquakes, acoustics, optics and chemistry. It is based on orders of magnitude, rather than a standard linear scale. == Common usages == The following are examples of commonly used logarithmic scales, where a larger quantity results in a higher value: Richter magnitude scale and moment magnitude scale (MMS) for strength of earthquakes and movement in the earth. ban and deciban, for information or weight of evidence; bel and decibel and neper for acoustic pow...

whic inclues this graph:

In the top left graph, the blue line.

that's the log scale.

the blue line becomes flatter, and flatter, and flatter.

as you go beyond the right margin, you find the log scale is, for practical computational purposes, flat

Simon André Forsberg

TTGTB, seems like @rolfl has the complexity things covered

btw, my new tag was removed from here: codereview.stackexchange.com/posts/61037/revisions

TopinFrassi

Oh okay, so the performance hit of the increasing number of data becomes more and more insignifient, which is why it is O(1)?

@SimonAndréForsberg TTGTB? Another meme?

Simon André Forsberg

@TopinFrassi Time To Go To Bed

TopinFrassi

Oohh okay! Good night!

rolfl

Aug 26, 2014 01:05

@TopinFrassi Which is why, beyond a certain point, increasing the size of your data has no appreciable impact to the performance of a binary search

why, after say 100 members in your data, when you go to 200 members, you will not likely be able to measure the change in speed of the search.

TopinFrassi

Indeed, it is way too small

rolfl

And, once you have something like 1000 members, in order for the search to take twice as long, you need..... go to 2^20 members.

which is a lot.

TopinFrassi

Yep, I understand that

rolfl

That is the power of the algorithm, not the implementation.

mjolka

2^20 isn't that much

rolfl

Aug 26, 2014 01:08

It is easy to take a badly implemented binary search, change a line or two, and halve the execution time.

without changing the algorithm.

or the complexity in which it scales.

just because the algorithm is a good one, the implementation can be slow.

Now, sort algorithms are often approaching O(n log n) performance (quick sort, etc.).

TopinFrassi

Isn't there some... "perfect" implementation examples. I mean, the binary search algorithm is quite clear in how it works, why is there multiple implementations of it?

rolfl

For example, a quick sort that, uses floating point math to find the midpoint instead of integral shift is slow.

mjolka

@TopinFrassi googleresearch.blogspot.com.au/2006/06/…

"The version of binary search that I wrote for the JDK contained the same bug. It was reported to Sun recently when it broke someone's program, after lying in wait for nine years or so."

rolfl

That's a bug, not a performance problem.....

mjolka

yep, just saying it's not easy to get right

rolfl

Aug 26, 2014 01:13

Consider a quick-sort for integers that, for some insane reason, does data[left] - data[right] == 0 instead of data[left] == data[right]

they are both going to scale at a complexity of O(n log n), but one will be faster.

(or, to make it really bad, consider a comparison of String.valueOf(data[left]).equals(String.valueOf(data[right]));

It will work.... but.... shoot me now!

TopinFrassi

I believe it wouldn't be much faster? But I understand the point. And @mjolka, I understand that the algorithms are theoricaly awesome, but the implementations are yet to be better (I'd need to get on English SE to see if that is a correct sentence..)

Mat's Mug

@RubberDuck how else would you write a data layer that can be mocked, making your app testable offline?

rolfl

@TopinFrassi - here's an interesting example of log-n performance, netflix.

Netflix can double it's subscriber base, at very little additional cost.

Netflix has these nodes that contain the bulk of their content in a storage rack and distribution node.

Thnk of a computer rack with a bunch of disks and some network capacity

They distribute their content to a top-level tier of nodes, say, 100 of them spread around the world.

then, these nodes in turn distribute the data to another 100 in smaller regional ISP server rooms.

which in turn distribute the data to what is now 10,000,000 users world wide.

Mat's Mug

@rolf mind if I bookmark this conversation? I'm missing it all and I'll want to read it later ;)

2

TopinFrassi

It's a kind of binary tree?

@Mat'sMug how can I do that, there's a big probability that I'll reread it more than once to make sure it is well written in my head

rolfl

Aug 26, 2014 01:22

It is a heavy investment in infrastructure, but, now, to add another million subscribers, all they need to do is add a server rack here or there, and not even worry about their central bandwidth.

@TopinFrassi exactly.

except it's almost Log100

TopinFrassi

Facebook does the same thing with it's Pictures caching I think.

its*

rolfl

indeed, many ssytems invest heavily, in complicate dinfrastructure, that just scales well.

once you get beyond a certain threshold, the additional scale becomes.... not so expensive.

Slide 21 has my favourite, the chaos monkey! : slideshare.net/adrianco/netflix-global-cloud

TopinFrassi

I can't thank you enough for the time you took to explain me all this!

The 2nd Monitor

Participants