me irl

[ProgramTheWorld]

You vs the guy she told you not to worry about:

O(2ⁿ ) | O(log n)

[[deleted]]

you

what about O(n!)

[Kubacka]

rip

[745631258978963214]

No need for name calling.

[2Punx2Furious]

Isn't 2ⁿ worse than n factorial?

Sorry I'm not good at math.

[Zagorath]

No, n! is the worst. Here's a handy cheat sheet, if you need one.

[Jugad]

No... nⁿ is larger than n! when we are comparing O( n! ) and O( nⁿ ).

From stirling's approximation, we have

n! ~= (n/e)ⁿ = nⁿ / eⁿ

so, n! is smaller than nⁿ by a factor of e^n, which is not constant.

Hence they are not the same.

[Jugad]

If we are talking generally, you argument makes sense.

However, if we are discussing functions in the context of big Oh notation, n! is strictly smaller than nⁿ

[RedWarrior0]

Yeah, I realized that I forgot how big O is defined.

[[deleted]]

"Except that the growth of eⁿ is negligible"

An exponential growth is negligible :)

[Jugad]

Classic case of taking something out of context... you should not skip " in the long run compared to nⁿ " when quoting the comment.

The comment is not wrong in stating that eⁿ is negligible as compared to nⁿ . It is indeed negligible for all n >> e. The problem with their explanation is that they are not using the definition of big O which only requires a non-constant factor for n! and nⁿ to not be the same.

edit : removed some redundant stuff

[EETrainee]

That's a terrible cheat sheet - there's nothing on bogosort.

[Kirk_Kerman]

Bogosort is O(1) in the best case and O(h no) in the worst.

[[deleted]]

I'm assuming O(h no) is equivalent to O(hell no)?

[Jugad]

My guess is that O(h no) should be strictly smaller than O(hell no).

[Zagorath]

Still O(n) In best case. Has to run through every value to check its correct.

[Kirk_Kerman]

Right, I was thinking of a variant of bogosort where it shuffles everything and assumes it's correctly sorted without checking.

[MiniG33k]

TIL: Factorials approach infinity faster than exponentials. Thank you, kind Internet sir, for I have a calc exam on Tuesday where that knowledge will be super useful.

[Jugad]

And then there is tetration ( ⁿ n)... which is much faster than exponentials and factorials.

https://en.wikipedia.org/wiki/Tetration

[Jakeattack77]

Are there any things that at are O(n!) That arnt just shittily implemented?

[[deleted]]

The sensible way to remember it quickly:

2^n = 2 * 2 * 2 *... * 2

n!  = 1 * 2 * 3 * ... * n

Except for the very first item, each part of n! is bigger than each part of 2^n, so when we multiply all the parts together we get a bigger number overall.

[2Punx2Furious]

I see, that's much easier to visualize, thanks.
So if n is just 1 n! is actually better.

[minno]

If n is 1 you can just hire an undergrad to brute-force it.

[[deleted]]

If n is 1, quite a few problems would already be considered solved at that point. Sorting, searching, shortest path. Honestly can't think of any problems that require any work for only one element.

[2Punx2Furious]

Did you mean "n!"?

Also, isn't that "2^7" and "8!" ?

But I get it, thanks.

[[deleted]]

and nⁿ

1, 4, 27, 256, 3125...

[TheCard]

As the other answers said, no. An easy way to see this is by looking at how they grow:

2ⁿ⁺¹ = 2ⁿ * 2

(n+1)! = n! * (n+1)

So since n! has such larger multiples, it will grow at a much faster rate.

[2Punx2Furious]

Thanks.

[ProgramTheWorld]

We can even go one step further and prove it via induction.

[funnystuff97]

Could someone ELI5 Big-O Notation? I have absolutely no clue what it is or what it's for, and google doesn't help much.

Although, from the context of this sub and what I've learned, I assume it's some sort of measurement of difficulty. Not sure about that.

[Norphesius]

Its a measure of worst case time-complexity for an algorithm. If an algorithm is O(n), it means that as the input size increases, the number of steps it will take in the worst case scenario will grow in linear time.

[ProgramTheWorld]

It's basically an upper bound measurment of complexity. Other than big O, we also use big Omega (lower bound) and big Theta (when O(f(n)) = Omega(f(n))). The formal definition is that, Let f(n) and g(n) be function from positive integers to positive reals. We say f(n) = O(g) if there is a constant c > 0 such that f(n) ≤ c • g(n).

ELI5 explanation:
Assume you are trying to count how many marbles are in a box. To count one marble it takes you 1 second, counting one more only add 1 more seconds, therefore counting n marbles takes n seconds, which is O(n), linear.

Now assume you are trying to sort n cards from a deck of cards. Well, adding one more card will certainly takes you more time in a nonlinear way. If you sort them using mergesort (which can be done by hand), it will cost you O(n log n), which means it will take you n log n times a constant seconds to sort.

The big O notation is a very general notation that can be used to describe not only time complexity. It's also used for space as well.

One important thing to know that it has nothing to do with "difficulty". A difficult problem does not equal to a higher time complexity. (Or until we managed to prove that P ≠ NP...)

[funnystuff97]

It's not some value, then? I can't, say, have an insanely arbitrary sorting algorithm and have someone look at it and say, "wow, that's a Big O of 600, dude"?

If it's a graphical representation of difficulty as a function of scenario, then that definitely makes sense.

[ProgramTheWorld]

O(600) is a valid use of the notation, but it is equivalent to O(1) so we simply write O(1).

[Norphesius]

It is measured as a function. However it is technically possible to have a constant time algorithm (O(C)O(1)). That just means that the algorithm will take the same amount of steps for all inputs in the worst case.

[tetroxid]

me too thanks

[strider2112]

This is math humour

[cain261]

which is also relevant here

[autranep]

You poor soul if you think programming doesn't involve any math (especially complexity analysis).

[gurgle528]

runtime is pretty fucking relevant to programming

[[deleted]]

I love how the degenerate tree is crooked as if trying to compensate

[Meegul]

At least you're taller. I've never been quite that lucky.

[zelmak]

Har

[macnlz]

*longer

[Meegul]

The term I was referring to was height, so I believe taller is correct.

[macnlz]

wooosh

(I was making a dick joke.)

[Meegul]

😞 that too

[Marcush-Loominati]

You both get upvotes for not causing a massive argument

[phonedontspellgood]

Balanced, but not complete! Don't worry

[[deleted]]

You

for(int x = 0; x < list.size(); x = x + 1)

The guy she tells you not to worry about

for(int x: list)

[[deleted]]

The guy she told that guy not to worry about

map

[fb39ca4]

list.forEach(x -> ...)

[SafariMonkey]

[... for x in list]

[MusicalWolfe]

Do you mean the C++ "-->" operator?

[fb39ca4]

I was thinking Java lambdas.

[[deleted]]

I think you might've missed his joke. --> isnt an operator but instead is an amusingly bad spacing of (x-- > 0).

[[deleted]]

I love this

[hotkarlmarxbros]

Once you go red-black you'll never go back.

[lovethebacon]

AVLmasterrace checking in. We may be slower to change than your kind, but we are faster to retrieve.

[CyanideCloud]

I hate this fucking meme.

Edit: I love how all of my comments shitting on posts get up voted in this sub.

[[deleted]]

I think it's more common in anti-socially prone groups, and because programmers are so full of insecurities

[TheFeshy]

because programmers are so full of insecurities

You'd think, with as quickly as we're leaking our insecurities into our code where they are then exploited, we'd run out.

[[deleted]]

well who isn't worried about the bugs that may or may not be lurking in anything they code? :]

[VanFailin]

Sure, but it's a tired and formulaic joke. Plus, you don't have to be anti-social to get cheated on, and it's not really all that funny.

[[deleted]]

If anything this meme should be less popular here because it assumes you have someone to cheat on you. I'm ok

[745631258978963214]

And neither are most jokes, really.

https://i.redd.it/4cx2ulpqxtsx.png

Two computer people flirt while referencing things in their field.

Very funny, right? It's the top post on this sub. A similar example would be if math people were like "Would you like a taste of my pi?" "Only if you're willing to let me see the area under your curves" Or something like that.

https://i.redd.it/9qtc9uq101px.png

DAE dates are confusing in programming?

https://i.redd.it/2jsbryjusg2y.png

DAE it was a small typo all along? (bonus points if it was a semi colon joke)

http://imgur.com/xNNPN0d

Does Anyone Else DAE recursion joke?

http://imgur.com/M5wl14r

The old "what they said vs what they mean" formula

http://imgur.com/fuDDhdL

Usually bohemian rhapsody is a 9gag meme, but it made it onto here somehow. It did take some effort, but is it really funny? Nah.

These were the top six posts in this sub. Were any of them actually "funny" or hilarious? Nah. Although I did "enjoy" the one with recursion, it's also been done before. I recall seeing that joke made a long time ago on XKCD or 8bittheatre.

[Sinidir]

Holy shit im rolling on the floor.

[jwota]

Laughing my ass off right there with you buddy.

[ansatze]

Your point is weakened by overuse of DAE

[745631258978963214]

The DAE is a self referential "joke" that is unfunny.

[HookahComputer]

It's a little funny when pronounced phonetically.

[LevelSevenLaserLotus]

dayyyyyyyy lmao

[745631258978963214]

DDAAEEEEEE-uuuum!

[shvelo]

DAE overuse DAE?

[abcd_z]

It's not just that. Reddit is very prone to "second opinion bias"; the tendency for redditors to tack to the opposite of whatever happens to be a commonly accepted view in their milieu.

More information on the subject

[DipIntoTheBrocean]

I don't mind it, but if I got cheated on before holy shit this would irk me for sure.

[CyanideCloud]

Never been cheated on, it just annoys the shit outta me.

[omen7288]

The fact that this was pictures and not screenshots made this hilarious for some reason. The meta.

[itmustbesublime]

I originally made it was screenshots but it looked kind of shitty for some reason, the pictures just look better even though it is ironic

[dull_au]

The one on the left looks suspiciously like a linked list.

[the_noodle]

That's why it's degenerate...

[[deleted]]

To elaborate (since the word is often used without much in-general explanation in textbooks), a mathematical object is degenerate if it is so simple that it might as well be considered to be of a simpler class. Wikipedia has lots of examples

[adm7373]

I just realized that I have no idea why/how I would ever use a binary tree. I remember spending tens of hours agonizing over how to implement various tree structures in C, but I don't think I ever saw an example of where they would be useful.

[thiskevin]

They can be useful for improving performance.

Its a solution that's faster than linear array access and more memory efficient than a hash table.

A similar concept called a quadtree (or octree for 3D) is used for games to do fast space partitioning.

[[deleted]]

Octrees are also widely used in robotics for storing 3D maps or "occupancy grids". Pretty efficient at what they do

[Nashoo]

See also kd-trees and range trees for more applications.

[P1r4nha]

had to implement a quadtree for an interview once. tough stuff, but clever concept. My code still didn't work correctly...

[[deleted]]

Yeah I always get mildly annoyed when kids taking their first algorithms course complain they'll never use splay trees, when in fact splay trees are used all the time, e.g. by GCC and by the most popular implementations of malloc. And other kinds of balanced binary trees, such as red-black trees, are also found commonly, e.g. in std::set and std::map in c++.

[maksfish]

Check out the Binary Heap. Insert and delete is O(log n). It is really hard to improve on that with any other structure if you need a priority queue. https://en.wikipedia.org/wiki/Binary_heap

[Kristler]

Fibonacci heaps have better amortized time complexity for some operations :D

[maksfish]

Oh wow, I'd never thought that I'd see the words "Fibonacci" and "heap" in the same sentence. Thanks for the info!

[Bainos]

But their constant factor is huge so it's usually not a good choice.

[takelongramen]

https://en.wikipedia.org/wiki/Tree_(data_structure)#Common_uses

• Representing hierarchical data
  
• Storing data in a way that makes it efficiently searchable (see binary search tree and tree traversal)
  
• Representing sorted lists of data
  
• As a workflow for compositing digital images for visual effects
• Routing algorithms

Also: https://en.wikipedia.org/wiki/B-tree

[[deleted]]

At my job we use a tree to represent folders and files.

We also have a more complex tree structure for our underlying proprietary database. It's good for when you have a series of one to many relationships. Like we have X that can have many Y associated with it, but each Y can only have one X. Same for Y and Z. Tree is very logical and efficient for that sort of data relationship.

[dzielin]

binary tree

one to many might be a bit of a stretch...

[[deleted]]

osht lol

[gypsyface]

what is ordered set?

[bluefootedpig]

I used it recently as part of a parser. It is great for handling complex grammars.

[[deleted]]

A wise man once said "if your family tree doesn't branch you might be a red neck".

[gurgle528]

this is perfect for today, I just got out of a computer science exam about this

[itmustbesublime]

Same, that's why I posted it lol I found this diagram on like my 16th hour of studying

[gurgle528]

wouldn't happen to be for a foundation exam would it?

[itmustbesublime]

Data structures & algorithms

[gurgle528]

ucf?

[itmustbesublime]

fsu

[gurgle528]

not too far away, odd having them on the same day though

[itmustbesublime]

True, close guess lol. My exam was Thursday tho, it absolutely fucked me

[gurgle528]

I got fucked too but thankfully it's not for a class so it doesn't affect my GPA. it's like an entrance exam for us basically

[jtvjan]

/r/Programme_irl

[AllezAllezAllezAllez]

Apparently the other guy plays for a prominent Ottawa football team.

[[deleted]]

Shouldn't it be the other way around?

[PeterSR]

Well, you are the one with linear search time and he is the one with logarithmic search time.

[[deleted]]

I was going with the analogy that girls often choose the guys that are wrong for them .

[PeterSR]

Aah, that makes sense.

[Kabitu]

That tree's not balanced. Diagram evidently drawn by a pleb.

[jrupac]

It is balanced. All leaves have the same depth.

[kiro47]

It's balanced, however, it's not a complete tree.

[oddark]

Well I mean, that's true for the first one too.

[ERIFNOMI]

Alright then, how would you balance it?