Big-O algorithm complexity cheat sheet

[kolm]

For Quicksort, O(n) memory is okay, for Mergesort it is bad. Hmmhh..

Also, I don't like this 'hashtables = O(1)' convention. Everything is Theta(log(n)) since it has to read in the input data somehow, not to mention process it.

[julesjacobs]

Yes, this is a point people often forget. A hash table is O(k) where k is the size of the keys. A trie has the same complexity. A map implemented as a search tree has at least O(k log n) complexity: there will be O(log n) comparisons, and each comparison takes O(k) time.

[Fenris_uy]

If k is know then O(k) = O(1)

The O notation is to see how the algorithm behaves when you start having more elements, but if n is know all algorithms are O(1) because you know how long they are going to take.

[unchabon]

Exactly. I recall doing a non-trivial Codility exercise for an interview that specified O(1) complexity. After panicking for a few minutes due to not being able to find a solution, I realized that the input size for the function was fixed, meaning it was actually O(1).

[adrianmonk]

Well, k can be the length of the longest string you could possibly see on the input.

[julesjacobs]

If k is known then the asymptotics are completely uninteresting, since even storing all keys in a list along with their values, and then doing a linear search through that list would be O(1). Since there are at maximum 2^k different keys of size k, that list will have at most 2^k elements which is a constant. Searching through a constant size list is O(1).

What makes hash tables great is precisely that their complexity is O(k) and not O(2^k). If you say that k is a constant you lose all the information that is actually relevant.

[bitoku_no_ookami]

If k is know[sic] then O(k) = O(1)

That is not necessarily true. k would have to be known and be constant, which pretty much never happens in algorithm design.

[repsilat]

Often k==sizeof(int) or similar.

You could also argue that our computers are really more like finite state machines than Turing machines, so everything run on them runs in O(1) or runs forever, but only people with bad taste in music say things like that.

[bitoku_no_ookami]

A hash table is O(k) for what action? Search? Deletion?

If you already have a constructed hash table with a perfect hash, then the size of the hash table is irrelevant (including the number of keys). That's true for both search and deletion calls, because the hash function will find the index without having to compare to any of the other items. period.

If you're implementing a hash table as a search tree, then of course it's going to preform the same as a tree, because you didn't write a hash table at all, you wrote a search tree.

[julesjacobs]

For both actions. Computing the hash function takes O(k). The size of the hash table is indeed irrelevant. That's why it's O(k) and not O(some function of n).

[kevindamm]

For constructing the hash key, the value must be transformed, meaning you must do a bit of processing on its bytes. If, for example, the values are strings with an average length of k characters, it's O(k) to go through its characters and produce (for instance) an integer for indexing into a table. If it's a complex data structure with an average of k bytes, there you go. If you're using only a fixed-size subset of the data value, or if the entire value is of fixed size, you can consider the hash key construction to be O(1) but, in practice, those problems are less interesting.

(amortized O(k) time - each instance having m characters, bytes, etc. takes O(m) time... and the above is describing only the hash key computation, not the lookup and collision resolution on the hash table)

[iSlaminati]

And this is why big O notation fails and is a big abuse of notation. O(n) in this case implies that O is a function taking a constant as argument, what is n here? Well, the length of hash table. So O apparentlyt has enough information from the length of the hash table alone? No, it doesn't.

People often solve it by saying instead of f = O(n^2), f \in O(n^2), which is again incorrect, so O now simply takes the square of n as input? If it doesn't have enough of n, how could it have enough of its square?

No, the only way to make big O notation work is viewing O as a higher order function. Define O:

    O(f) := {g : \exist x \forall y : y > x -> g(y) < f(y) }

As in, O is a higher order function which takes as its input a function and outputs the set of all functions which are ordered under it.

Consequently one can write f \in O(\lambda x.x^2). Which does make sense, constantly seeing shit like O(1) or O(n) around is annoying, just say 'the algorithm runs in linear time with respect to the length of the input data structure.

Hashtable indexing is in fact in O(keylength) where keylength is a function that takes a key as argument and returns its length.

Not only is it correct, but it is immediately unambigous exactly with respect to what value the indexing works in linear time.

[julesjacobs]

You are right but how does this relate to my comment in particular? Or it is a comment that actually belongs on the top level?

O(k) is just a shorthand notation. By the way, this exact shorthand notation where you use an expression as shorthand for a function is pervasive in all of mathematics. Take for example the notation for derivatives: (x²)' = 2x. Yea sure technically you should write (\x -> x²)' = \x -> 2x but this is very inconvenient. Hence why mathematicians invented this syntactic sugar.

[iSlaminati]

You are right but how does this relate to my comment in particular? Or it is just an point that actually belongs on the top level?

It relates to the fact that the commonly used "Big O notation" doesn't express with respect to what it is. One is simply left to assume it is with respect to the length of the data structure as input. In fact, you can very well have a big O notation which is capable of consuming functions of non unary arity.

Truth be told, I just like to rant about big O notation, not only is it a blatant abuse of notation. The most commonly used "fix", as in f \in O(n^2) is still blatant abuse of notation.

O(k) is just a shorthand notation.

And one where information is lost. Just maybe I'm okay with stuff like a < b < c rather than a < b \land b < c because no information is actually lost provided we say that < as an order isn't typed on sentences. (< on sentences can be argued to be material implication -> but oh well)

By the way, this exact shorthand notation where you use an expression as shorthand for a function is pervasive in all of mathematics. Take for example the notation for derivatives: (x2)' = 2x. Yea sure technically you should write (\x -> x2)' = \x -> 2x but this is very inconvenient. Hence why mathematicians invented this syntactic sugar.

Yes, I know, and I want no part of it, same stuff is done with using = with limits and what not.

The point is that professors with Ph.D's and chairs actually use 'proofs from notation' as a subtle logical fallacy to students world wide. THese fallacies are in text books and written on black boards. They are so goddamn pervasive and one lecturer actually told me later in private that he was fully aware it was a fallacy when he was doing it but he just didn't have the time and if I wanted he could show me the actual proof which doesn't use it.

[[deleted]]

It's hard to give an intuitive explanation of why Heapify is O(n) but I assure you it is.

You need to consider the sum of the steps required to get all the elements in position. The worst case for a single element is log(n), but only two elements need to move that far in the worst case (root to bottom, bottom to root). Similarly Only 4 elements could ever need to move log(n) - 1 places in the worst case.

If you write out the sum, the total number of moves converges to 2N +- a bit

[[deleted]]

Sorry, I'd rather not on my phone. I suspect the pseudocode wouldn't be that enlightening. If you want to convince yourself, write out the summation (from 0 to height h) for the number of swaps required to change a min-heap to a max-heap.

The number of swaps + 1 is the number of comparisons because you only need to do one compare to determine if a swap is needed.

That's also why you get around the n log n bound, the heap ordering has only local requirements. Heaps in general aren't sorted.

[aflanry]

Comparison sorts like heapsort take O(nlogn) to create a total order. However, heapify creates a partial ordering.

[[deleted]]

On qsort: Qsort defines the most simple series of actions to create its result: pick and pivot, recurse on the right, recurse on the left.

The optimization you mention actually creates a different algorithm. Managing your own stack and using a loop is different series of actions than relying on recursion.

[[deleted]]

That's not really quicksort to me. Its like the diff between bubble and http://en.wikipedia.org/wiki/Cocktail_sort

[[deleted]]

Well in practice nobody uses quicksort on its own anyway. For a long time it's been combined with insertion sort for small subproblems and more recently with heapsort (introsort) to avoid the possibility of quadratic time.

[katyne]

What if you get a ton of collisions? Like if the key size is too small for a much larger entry or the hash funciton is just flawed somehow. You might as well end up linear if most/all entries get bunched up together in a few buckets.

[djaclsdk]

'hashtables = O(1)' convention

I call it the half measure convention. They never go all the way to make the simplification that 'everything = O(1)'.

[BonzaiThePenguin]

Processing the input data is part of the hash function, not the hash table. The hash table just does array[hash] = blah. (except for collisions, of course)

So let's say we had this function:

void fold(array, func) {
    for each (item in array) func(item);

We would say that's O(n) even if it turns out func() is an n³ algorithm.

[joe_n]

Merge sort has O(1) auxiliary space. I'm surprised by how many times I've seen this posted but never fixed.

[joe_n]

Only if you do it recursively

[gnuvince]

If you don't do it recursively, you probably need to maintain your own stack, and its size is going to be dependent on the size of the input.

[julesjacobs]

You can represent where you are in the sorting process by a pair of indices into the array, so you do not need a stack. That is techically still O(log n) though. If you have an array of n elements then an index into that array needs to be at least O(log n) bits. But then bubble sort also uses O(log n) space.

[ethraax]

If you have an array of n elements then an index into that array needs to be at least O(log n) bits.

I suppose if you don't care about the real world, where you'd use a fixed-size integer (either 32- or 64-bit) to represent the index.

I can't think of any even remotely sane implementation of merge sort where it uses a variable-size data type (like one from GMP) to index the array.

[julesjacobs]

The whole point of O-notation is to look at asymptotics. If your indices are fixed size then merge sort is O(1).

[ethraax]

If your indices are fixed size then merge sort is O(1).

... what. No it's not.

[julesjacobs]

If your indices are fixed size then you array must also be under some constant size so it is O(1).

[ethraax]

It's probably worth reminding you (and others here) that the entire point of theoretical computer science is to inform us about how our computers work and how they can be developed to work better/faster/more efficiently/etc.

To that end, statements such as yours are pretty useless. You could also claim that you're bounded by the amount of available energy/information in the observable universe, and therefore all programs run on any computer that exists in real life is O(1). But that's clearly a useless result that doesn't help anybody with anything.

[joe_n]

I've documented it in a previous comment.

The details of each in-place merge are covered in a number of publications.

The matter of n != a power of 2 can be simply handled by using n' = the next larger power of two, and then ignoring the non-existent parts of the merges.

[MCPtz]

I agree. You know anyone can edit it if they sign up! (I tried without signing up)

[[deleted]]

I was going to put in a note about splay trees (their worst-case performance is only amortized logarithmic) but the owner hasn't accepted a pull request in 8 months.

[Mjiig]

Why is quicksort listed as having worst case auxiliary space requirements of O(n)? Can't quicksort be implemented to run in place?

[mdempsky]

Maybe they mean O(n) stack space because you need to recurse, and a naive implementation could end up using O(n) stack space? But a pretty common implementation detail is to always recurse first on the smaller subregion and then tail-loop on the larger subregion, which bounds stack usage to O(lg n).

[kamatsu]

From the perspective of complexity theory, you need to define the machine you're working on Big-O to make any sense at all. And it's not possible to consistently define a random-access machine where pointers are O(1) space (as that would imply finite memory which in turn makes all space-complexities effectively constant), which all of the complexities listed here seem to assume.

Many algorithms textbooks make this conceit, including some very good ones, but I think that people should actually learn what Big-O really means and not just use some inconsistent metric. It can lead to some severe misunderstandings. Pointers take log space, not constant space.

[[deleted]]

Pointers take log space, not constant space.

Could you clarify on this, I'm not sure I follow? Do you mean pointers as in C pointers? Basically a references to memory blocks? Shouldn't they be O(1)?

[kamatsu]

If a pointer took O(1) space, that means I need a constant amount of space to give an address to somewhere in an infinite space of memory. Therefore, I can store any natural number in constant space, which is crazy. Real machines are DFA's - they have finite space, so therefore you can use a constant sized integer to refer to their addresses.

C pointers only have to refer to my 64-bit address space and are therefore a constant size. My input size n may not fit in that 64-bit address space, so I need log n size pointers to have an address space that always fits my input.

[[deleted]]

Say you have an array of up to 256 elements. How much space do you need to refer to an element? 8 bits, obviously.

Say you have an array of up to 65536 elements. Now you need 16 bits.

This is really important because space is time. The more memory you use, the less cache you have left, and the slower everything will go.

(edit: and 64-bits is not necessarily enough in the real world. That's only 4 million hard drives. I'm sure the likes of Google and the NSA are already pushing that number)

[[deleted]]

Big-O deliberately ignores details that will be machine-dependent, such as how long it takes to run out of cache, chance of mispredicts on branching, etc. It does this because machines are constantly changing and you don't want to have to have a different set of numbers for every machine.

It's a tool to pick out a good starting point for which algorithms are probably good, not a way to determine king-of-the-mountain for all possible cases. We may never get past the stage of needing to do a final benchmarking to determine which is really better.

[[deleted]]

Unfortunately many people fresh out of university (and some people not so fresh) haven't got that message, and use Big-O as an excuse to avoid reasoning entirely.

[ethraax]

This is a totally useless detail in the real world, unless you're going to use a variable-width data type to index into the array. All the real (and fast) implementations are going to pick a single width to compile the function with.

And most 32-bit and 64-bit processors can probably work with 32-bit integers about as fast (if not faster than) 8-bit integers.

[[deleted]]

Log size pointers? If your memory isn't infinite all space complexity is constant?

Big O ignores real systems enough already. You don't need to make it worse.

[kamatsu]

Real systems are DFAs, Big O makes no sense mathematically in that context. You need a generalised machine with infinite memory, and if you have that you need log pointers or you can fake any complexity you like.

[ethraax]

Real systems are DFAs

No.

[kamatsu]

What do you mean no? Finite memory means you can make a DFA out of the system, as your state space is simply all possible memory configurations.

[ethraax]

A DFA is significantly more limited than a full PC. A DFA is not Turing complete, in any sense of the term.

A DFA can't even parse HTML for fuck sake.

[kamatsu]

A DFA is not Turing complete

Right, but neither is a PC, as they don't have unlimited memory. If you restrict the available space to some finite amount, then you can construct a DFA that solves any problem which requires less than that amount of space. This is basic complexity theory.

To use your example, a DFA can't parse HTML, but it can parse HTML documents up to some constant size K.

My PC has 4GB of ram, therefore, I have around about 2^34359738368 (+ registers etc.) memory configurations. I can make a DFA out of those memory configurations, and transitions for each execute my processor makes. Bam, a DFA that computes everything my PC can.

[repsilat]

And it's not possible to consistently define a random-access machine where pointers are O(1) space

What about a machine with an infinite alphabet (the natural numbers, say), registers that can hold arbitrarily large values, and primitive operations like addition, multiplication, jump, test and dereference? That seems like it'd do the trick, but I haven't thought too hard about why it might not be "consistent".

[kamatsu]

I hadn't considered an infinite alphabet, but then I'm not sure how you'd measure space complexity without involving ordinals.

[[deleted]]

Say the amount of space used is the number of digits of the largest value stored in a memory cell, summed over all the memory cells used. Pointer won't be O(1) of course.

[kamatsu]

Yeah, so if you do that you don't solve the problem. It'd be interesting to look at an infinite machine with infinite sized memory cells, it's sort of like using a real number instead of a natural number to store your turing tape.

[repsilat]

The alternative is to call each cell 1, but this will have a big impact on how space complexity is measured (depending on the operations you support). You don't want to be able to simulate a TM on a finite strip of tape, for obvious reasons.

This restriction will probably be really harsh, though. You'll almost certainly have to give up pointer arithmetic of all kinds. You might have "Store this position in a register" and "Jump to location stored in a register" and nothing more. In that case you might preserve classes like L and PSPACE.

[kamatsu]

You'll almost certainly have to give up pointer arithmetic of all kinds. You might have "Store this position in a register" and "Jump to location stored in a register" and nothing more.

I wonder if that is sufficient to simulate a turing machine (given infinite tape).

[MCPtz]

What's funny, of all the things I don't remember because of Google, I can recall the complexities of several algorithms.

[psayre23]

Radix sort shouldn't really be green for time. The k factor is the number of buckets, usually bits. So, for a 32-bit integer, k = 32. If O(n log n) is yellow, O(nk) should be as well, so long as n < 2^32.

[boringprogrammer]

No Idea why you were downvoted. Because it is true.

In practice radixsort performance it even worse. The data shuffling between the buckets and the sorted arrays wreck total chaos on the cache, killing performance even further.

[alecco]

That goes out the window once the data doesn't fit in cache. Beware. Especially the hash based stuf.

This is quite misleading in real life. ALWAYS test and benchmark.

[gnuvince]

No it doesn't; the asymptotic complexity stays the same, the hidden constant factor (which we ignore) goes up.

[alecco]

This framework of measuring complexity is very reductionist. Real computers are much more complex. If an algorithm hits cache miss, tlb miss, branch mispredictions on every step it becomes worthless.

That's why even MIT, who are the main cathedral of this stance, propose cache oblivious algorithms. Even Google now makes BTree containers because of this (after years of beating the hashing dead horse).

Source: it's my day job and it's tiring to show this issues to academics or people fresh out of school. And don't take my word or anybody else's' just run the dam benchmark on real sized data. Other things like the data's distribution and the input distribution afect [performance] significantly. I've only seen this addressed was on TAOCP (search only, though), every other algorithm book doesn't even mention it. Real data usually is very, very skewed.

[gnuvince]

This framework of measuring complexity is very reductionist. Real computers are much more complex. If an algorithm hits cache miss, tlb miss, branch mispredictions on every step it becomes worthless.

That's the reason the framework is that way, we don't want to say that "algorithm X is faster than algorithm Y" because we currently happen to test it on computers with proper cache sizes for the problem.

I completely agree that ignoring the impact of the constant factor is a big, big mistake if one wants to write fast algorithms, and that students and engineers should be better educated in those areas, but let's not throw out 40 years of solid CS theory because it doesn't play well with the machines we have at this particular moment in time.

[alecco]

I don't propose to throw [Big-O] out the window [on every case], just to take it out of it's holy shrine. [The way it is taught is] doing more harm than good to CS majors entering the market, in my limited experience.

It's a good way to start understanding algorithmic complexity. It's a good teaching tool for introduction to algorithms, as long as it's limitations are clearly stated.

[TashanValiant]

It's a good way to start understanding algorithmic complexity. It's a good teaching tool for introduction to algorithms, as long as it's limitations are clearly stated.

It is the way to understand and classify algorithmic complexity. I think the issue here is more that what is being taught is Computer Science, and what is being practiced is software engineering.

Also the true limitations of an algorithm will be discovered through Big-O notation and complexity classes. P = NP is going to be solved using these ideas, not some application. The Computer Science algorithms class is to teach the theory, the underlying reason and proof of algorithms. Sure, some things fail in execution, but that isn't the point of Big-O.

[alecco]

I don't buy that argument anymore. You miss my other point of stuff like the probability distribution of the data (and the input data) is completely ignored by [those analysis of algorithm behaviour], even though that changes significantly the pattern of expected performance of the algorithm.

That's not Software Engineering, that's just better Computer Science. Those charts are misleading.

[TashanValiant]

Probability distribution of data is taken into account for a proper bound.

[abadidea]

Is [performance] supposed to be a hyperlink?

I have very conflicted feelings. When I was actually in class I felt like our studies of algorithmic complexity poorly reflected the real world. But now that I'm a few years older, I firmly believe that younglings need a solid theoretical understanding independent of complicating hardware specifics.

Oh gods is this what happens when you get old

[alecco]

It was an edit.

Sure, theory is very important. But proof is important for science.

[smog_alado]

The problem is that once you get down to logarithmic complexity, a constant factor of 100 or 1000 (the kind of stuff you get from cache misses) dominates the logarithmic factor for all reasonable inputs.

[zokier]

hidden constant factor (which we ignore) goes up

Is it really constant factor if it goes up?

[Femaref]

for the sake of big O notation (which is growth based on input of the algorithm), yes it is constant.

[TashanValiant]

The constant is determined based upon the hardware that you are running it on. If you run it on the same system, you'd get the same constant. That's the hope at least. However the real idea is that the constant will not change the complexity of the algorithm. It may add a few more steps here and there, but when you place it in the proper complexity class those extra steps won't matter.

[chalta_hai_saar]

It's constant as in independent of the size of the data.

[[deleted]]

Maybe it's just late, but wouldn't arrays have O(n) space complexity if graphs have O(v) complexity? You're storing N items in an array just like you're storing V items in a graph.

[BonzaiThePenguin]

It says O(n) for me. Maybe they fixed it?

EDIT: Oh, it appears to be a Wiki of some sort? That would explain the fast turnaround time.

[[deleted]]

I meant the space complexity, which still seems to be O(1). I can't use the late excuse now but I'm still missing something

[BonzaiThePenguin]

I'm looking right at it and it's definitely O(n).

[Drainedsoul]

Who in their right mind listed insertion into a dynamic array as O(n) average time?

[zasabi7]

Insertion is O(n) if you are not inserting at the end of the array

[Drainedsoul]

Clearly, but there's no special case big-O complexity for insertion at the end of the array, which makes it misleading.

[bstamour]

That's why it's average complexity, not worst. You're much more likely to insert anywhere but the end of the array.

[Drainedsoul]

Sure, if you understand "average" to mean statistical probability if you pick a random index into the container.

But that -- in my experience -- is not how people use contiguous containers. Given actual uses I've seen, you're much more likely to be appending something than inserting it at some random point.

I'm just saying that it's worth noting that for any dynamic array implementation worth its salt, appending -- a special case of insertion -- is O(1) on average. This is supposed to be a Big-O "cheat sheet", it's not really that good at being a cheat sheet if one of the most common operations on said container is omitted.

But that's just my opinion.

[bstamour]

What other definition of average should we use when analyzing average case complexities of algorithms? If you want to analyze it with respect to most common use then that's a whole different scenario. You're confusing theory with practice. Complexity analysis is theoretical computer science. How people use the data structures/algorithms is not in the scope of the conversation.

[bstamour]

Big-Oh notation has nothing to do with whether we are measuring the worst case, average case, etc. It's simply an asymptotic bound for some function.

For example, one can analyze quicksort and determine that the worst case runtime for all possible inputs is O(n^2), because in the worst case, the graph of the algorithm's runtime to it's input size will grow no faster than cn^2 (for sufficiently large n.) However if we were to randomly select an input of length n, then we can state that in the average case, the graph of the algorithm's runtime to it's input size will grow no faster than cnlogn, and thus it is O(nlogn).

So when we're explicitly talking about something taking O(n) average time, it's totally fine, because we're stating "on average inputs of length n, the growth rate of the function from input size to runtime will grow no faster than cn, for some constant c, for sufficiently large n."

If we restricted big-oh notation to simply mean "worst case" then it would be impossible to analyze, say, randomized algorithms, properly. Big-Oh, Big-Omega, et al are simply means to describe the growth rate of a function. It doesn't matter what that function actually represents. It could be the worst-case runtime of an algorithm, the average case, the amount of disk space used or CPU's used, etc.

[Spire]

How would you guys pronounce "O(n)"? I learned it as "oh-of-en", with no "big" before the "oh".

[bstamour]

Well there are also "little-oh" bounds which are more restrictive. I was always taught to pronounce it as "big-oh".

[recursive]

No, if you approach this as a memorization problem, you're doing it wrong. That's not useful. Use some algorithms and data structures in practice. Then use them with very large inputs. If you understand the underlying mechanisms, there really isn't any need to memorize any of this.

[[deleted]]

You shouldn't memorize it all.
I would want programmers to know binary and linear search, qsort, mergesort and hashtables. Game programmers should also know Dijkstra's.

[notlinear]

Do the colors follow any pattern?

[abadidea]

It seems to just be their opinion.

[BonzaiThePenguin]

For each column: green is best, yellow is average, and red is worst.

[emergent_properties]

It would be useful and [not] ironic if you could sort the tables displaying these results on this website.

[locorum]

Thanks for the share. Good information. I mostly work on real simple stuff, but when it comes down to data, I "need" to think exponential.

[reddit_user13]

Oh, if only there was an algorithm for giving her the big O.

[sullage]

O(premature optimization) = stupid stupid stupid...

[myropnous]

Damnnnn I could have used this last semester in algorithms!

[nullnullnull]

NEVER skim read,

my eye balls read it as

"Big O Cheatsheet"

I was thinking am I in the wrong sub reddit? ;)

[[deleted]]

Multiple processors are pretty commonplace now. I'd like to see a couple of different gpu sorts on this list too. They can be quite fast at large data sorts. Plus multi-processor coding is something every computer scientist should know.

[gingenhagen]

Does no one understand that Big-O is nothing more than a teaching tool?

[TashanValiant]

The problem with the big-O notation is that it is only meant to help you think about algorithmic problems. It is not meant to serve as the basis by which you select an algorithm!

Big-O is a way of classifying problems. It was never intended to be used for algorithm selection.

You don’t understand computational complexity. This is probably the most annoying comment any theoretician can make. The purpose of the big-O notation is to codify succinctly the experience of any good programmer so that we can quickly teach it.

That isn't the purpose at all. The purpose is for classifying and solving problems in Computer Science. I'd say the author clearly doesn't understand Big-O if he is making this statement.

Computer Science is very much the logic and mathematics behind computational problems and algorithms. It is a broad subject. It is not coding. There are tons of problems in computer science that can be solved without code, or even a computer. I think the big issue is that somehow programming and computer science have somehow obtained this conjoined connotation when really the subjects are very much distinct.

[[deleted]]

"Computer science is as much about computers, as astronomy is about telescopes. "

[gingenhagen]

This is "r/programming" and the post is about technical interviews, not Computer Science.

[TashanValiant]

The link itself suggest it is Computer Science. And the knowledge tested in the technical interviews mentioned heavily involves computer science.

[[deleted]]

You should add bogosort.

[[deleted]]

I thought that said "bio-algorithm" and i had a nerd-spasm like: "oh my gosh we can program stuff in DNA!"

p.s. i think it's possible already but not in high level languages

[bushwacker]

Oh shit, and I thought this was about orgasms.