The 2nd Monitor

Phrancis

11:18 PM

Anyone can tell me what the O stands for (is it an actual word?) in something like O(N)?

nhgrif

0

A: Complex Conditionals in a Strategy Game

I should note that when it comes to bitwise conditionals such as (floor.floorBuildState & FloorHasLadder) and (floor.floorBuildState & FloorHasWalls) == 0), my understanding is that you should not pass those back directly such as return (floor.floorBuildState & FloorHasLadder) but shou...

O is used because the notation represents the order of the function.

Big O notation

In mathematics, big O notation describes the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann–Landau notation (after Edmund Landau and Paul Bachmann), or asymptotic notation. In computer science, big O notation is used to classify algorithms by how they respond (e.g., in their processing time or working space requirements) to changes in input size. In analytic number theory, it is used to estimate the "error committed" while...

mjolka

@Phrancis en.wikipedia.org/wiki/Big_O_notation

Dan Lyons

heh I was gonna post that if/when I found where the wiki article actually specified what O stood for (if anything)

nhgrif

> The letter O is used because the growth rate of a function is also referred to as order of the function.

That's in the wiki.

Phrancis

Ahh, thanks guys, something I will enjoy reading about (as it sounds important)

nhgrif

11:23 PM

Eh, I'm not sure how important it necessarily is to understand the notation completely unless you're doing some highly theoretical stuff.

What's important to know about the notation is that the smaller the part in the parenthesis, the better.

Phrancis

OK. Well, good to know a little about at least I hope

> You have fully used your vote allowance for today

RubberDuck

Well, if nothing else, it's good to understand it just to keep up with conversations around here.

DVLR

nhgrif

It's like learning geometry theory versus having a measuring tape to measure what you need to measure.

If you're doing theoretical work, it's important to know all the theories and formulas and such.

RubberDuck

Ahhh, but what if I don't have a tape measure handy? =;)-

nhgrif

If you're in the field and need to know how big something is, measure it.

Dan Lyons

11:25 PM

Even in practice, it's decently important to understand scaling complexity

Phrancis

@RubberDuck DVLR?

RubberDuck

Daily vote limit reached.

mjolka

@nhgrif i'd disagree, i think it's good to have a grasp on the actual definition

Phrancis

Ah

nhgrif

It's important to understand scaling, but personally, I don't understand how to figure out exactly what the O-notation is of something I just wrote.

But I can look at two code snippets and tell you which one is less complex (and would have a better O-notation)

But it's never even remotely important for me to know what the O-notation of a snippet I just wrote is

Dan Lyons

11:27 PM

O(n) is basically an operation which iterates over a collection of items, where n is the number of items. Each level of loop nesting multiplies the ns

mjolka

@DanLyons no...

RubberDuck

I think so too @mjolka. For example, it's important to note that two different O(n) algorithms can have very different runtimes on the low end of the scale. Because both O(n) and O(2n) are designated O(n).

If I understand correctly.

nhgrif

That's actually evidence for my point @RubberDuck, I think.

mjolka

@DanLyons or are you saying that iterating over a collection of n items is an example of an operation that takes time O(n)?

nhgrif

It's not important for me to know the O notation. It's important for me to know the realtime runtime.

RubberDuck

11:29 PM

I can see that stance. Knowing the notation just helps further that understanding.

Dan Lyons

@mjolka yeah

RubberDuck

It makes it easy to talk about.

nhgrif

My end-users couldn't care less if it's O(n) or O(n^5)

mjolka

@DanLyons ok, i thought you were giving a definition the way it was worded :)

Dan Lyons

say that when n grows large :P

mjolka

11:29 PM

@nhgrif they most certainly will :)

RubberDuck

Oh, but they do @nhgrif. =) they just do to know they do.

nhgrif

If I can guarantee my n will always be very small and my O(n^5) is somehow faster for very small n, then O(n^5) might be a better choice.

I don't know if I could come up with a concrete example of that, but the point is...

Dan Lyons

if you can make that guarantee, yes

nhgrif

O notation is about which algorithm should be better as n approaches infinity.

In practice, n is never infinity. It can be large, but definitely never infinity.

Captain Obvious

0

Q: Number Gusser in c++ using function and midpoint

I am trying to write a code for number gusser using funcitons: The playOneGame function should have a return type of void. It should implement a complete guessing game on the range of 1 to 100. The shouldPlayAgain function should have a boolean return type. It should prompt the user to determine ...

c++

0

Q: GemStones Hacker Rank solution 1 test case failing

import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { public static void main(String[] args) { /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */ ...

java

Phrancis

11:31 PM

@nhgrif TSA

nhgrif

So, you find or come up with the best algorithm you can for your scenario. You test it with several different possible scenarios, try to find the worst case scenario.

Dan Lyons

it doesn't take a very large n for high-exponent or factorial algorithms to bite you, though

Phrancis

I'm learning new stuff today!

2

nhgrif

If your worst case scenario is fast enough, then you're done.

RubberDuck

That's my theory when writing queries. ^

nhgrif

11:32 PM

If your worst case scenario is too slow, you might try to optimize. But speeding up worst-case scenario at the expense of slowing down best-case scenario may or may not be worth it.

Dan Lyons

for example, I found one piece of code which was O(n^2) that took 10 minutes to process with 10k items that dropped to 0.8 seconds after making it O(n)

nhgrif

You still have to take into consideration how likely a worst-case scenario is versus best-case scenario.

mjolka

@Phrancis here's a good exercise. using the definition here en.wikipedia.org/wiki/Big_O_notation#Formal_definition prove that f(n) = 3n + 2 is O(n)

nhgrif

@DanLyons My example was extreme, and it's unlikely that I could come up with a concrete example that fits my hypothetical, but the point is, all the user knows is a rough estimate of the actual time the operation took.

I write code in the best way I can think of. Then I see whether or not it's too slow. If it's too slow, I try to find ways to optimize it.

At no point do I ever take time out of my day to figure up the O-notation of anything I write, ever.

RubberDuck

This is actually a pretty good primer to figuring out why `f(n) = 3n + 2 = O(n)

►

ZEQUELS!

nhgrif

11:37 PM

Basically, say I have a triangle.

Not a triangle drawn on a piece of paper, but actually cut out of the paper.

Figuring O-notation is like using pythagorean theorem to find the length of the hypotenuse. Whereas I'm more likely to grab the measuring tape and just measure the length.

And once we consider that it might not be a perfectly right triangle, or that the hypotenuse might not be a perfectly straight edge, and so our pythagorean theorem is a good guesstimation but not perfectly accurate, we then realize the value of actually just measuring it.

mjolka

@nhgrif i appreciate the value in measuring; it's always a good thing to do. but a geometer will be poorer for not knowing the pythagorean theorem. big-O notation is another tool for the toolbelt

Phrancis

@mjolka I have no idea... not very skilled in mathematics at the moment

200_success

Looking forward to your Project Euler #1 in SQL.

Phrancis

You can do Euler in SQL? Sounds odd lol...

nhgrif

SQL has functions and stored procedures. Why wouldn't you be able to do PE in SQL?

Dan Lyons

11:46 PM

Big O and actual measurements don't really compare with one another. The better geometry analogy is to call a performance measurement a point while a Big O formula is a line.

Phrancis

I guess, maybe I'll give it a try. Seems... unconventional

200_success

That was a bit of a joke.

nhgrif

I disagree Dan...

200_success

#1 is totally possible in SQL, though. You probably wouldn't want to do the more advanced ones in SQL.

mjolka

@DanLyons well you could repeat the measurements and get a scatter plot :)

Dan Lyons

11:48 PM

Yeah - taking a bunch of performance measurements would create a scatter plot, and the Big O notation would be the regression line.

nhgrif

So, realistically, the O-notation is more like the function.

Not a line.

n is the x, and the time (or memory size) measurement is the y

Except that two algorithms with the same O-notation can have very different measurements.

mjolka

@Phrancis the definition on wiki might not be the most friendly introduction. if you're keen to learn, i'm sure google will turn up a better introduction to big-O

nhgrif

And all the same, what's actually valuable is the actual time measurement.

Captain Obvious

0

Q: Which is a better implementation of a stack data structure (based on an array)?

This is a version I made : #include <stdio.h> #include <stdbool.h> #define MAX_STACK_SIZE 255 typedef struct { int array[MAX_STACK_SIZE]; unsigned int count; unsigned int max; } Stack; void initialize(Stack*); void push(Stack*, int value); int* pop(Stack*); bool isEmpty(Stack*); b...

c data-structures stack

nhgrif

And given that two algorithms with the same O-notation can have very different measurements, we can infer that a more complex O-notation can possibly have better measures than a simpler O-notation for small values of n

Though as n approaches infinity, the simpler O-notation will have the better measurement.

mjolka

11:52 PM

@nhgrif i was having trouble analysing the time complexity of someone's code here on CR, so i did the obvious and put in a printf of the number of relevant operations. put the numbers in excel, and the line of best fit was (1/10) * n^3 + O(n^2)

gotta say, i am still baffled by the factor 1/10

nhgrif

But that's measuring the iterations, not the actual time (or space)

I can write two for loops that you'd think were identical and I'll tell you that one will run significantly faster than the other.

mjolka

yeah i know. i'm not arguing anything, just wondering how on earth the 1/10 came out of the algorithm

2n^3, sure. 3n^3, why not. but 1/10?

nhgrif

In the Swift playground, you can probably more easily figure out your O-notations, as it will tell you how many times a function is called or how many times a loop is iterated.

Without any print statements

mjolka

that's cool

how're you liking swift?

nhgrif

It still needs some work.

Anyway, on this O-notation stuff, at the end of the day, if you have two horses, the best way to figure out which is faster is to just race them.

And once you figure that out, before you start wondering if there's an even faster horse, you first need to ask yourself whether or not this horse is too slow.

Phrancis

11:57 PM

3 minutes...

RubberDuck

Do you need a star @Phrancis?

Transcript for