The first class that touched upon the formal theory of limits for me was called 'Analysis'. The calculus courses I took before that were informal and leaned mostly on intuition and algebra.
I attempted to use only intuitive explanations in my programming class once, and a student rebelled and asked for some more definite rules. She wasn't asking for a dictionary, just SOME structure to help her out. The conclusion I reached is that you need a mix - ground students in rules while supplying them with high-level concepts. You shouldn't rely on only one approach, but give them multiple entry points into the idea. Moderation, as in all things.
This is everything I hate about language learning through pure immersion (Duolingo, Rosetta Stone, most language schools). For example, I struggled for an absurdly long time with genders in German when I started because I assumed it was like French (male, female, plural). Turns out there's 4 genders, and often the female article is the same as a the plural. Once English sentence could have solved that.
There are three genders in German. And four cases. Multiply them together, throw in plurals, add in uses of the indefinite article and the definitive article, and, well, it is far too much for a single sentence to explain.
But in principle I agree with you. We need a bit of book learning to go with the "just start speaking" approach.
Hence the 3-dimensional chart for determining adjective ending -- it depends on gender, case, and the word preceding it (i.e., definite article, indefinite, or nothing). Although I found a chart on this page that "reduces" it to a four-branch flow chart:
I think that learning the rules is an absolute necessity, even if your goal is to develop your intuition well enough that you don't need them. (Edit: I think this implies a little more than I meant to say. Being exposed to the rules is a necessity, but you don't necessarily have to go out and memorize them from beginning to end or anything.) They're important scaffolding. Even native speakers of a language need to be taught the formal rules if they're to speak well.
I'm going to make a lame attempt to coin a term and call this the Arch Fallacy, which is when you look at your goal and assume anything not present in it is unnecessary to achieve it. A completed arch contains no supports within it, but you'll have a tough time building one without any.
"contains no supports" (was "contains to supports")
Funny thing is on first reading, I didn't notice that at all and read it the way you meant. I only saw the typo on a second reading. Interesting autocorrect the brain does.
In any case I like your Arch Fallacy! I think I will use it.
> In any case I like your Arch Fallacy! I think I will use it.
I'll use it too, it's great and I don't recall any term for that particular error in thinking. I've already started spreading it (the name, not the error) among friends, hoping it will catch on.
> Even native speakers of a language need to be taught the formal rules if they're to speak well.
Native speakers are taught some rules, but many are rarely taught unless a student has learning difficulties. The adjective ordering that OP mentions is a solid example. Others include aspiration of stops; voicing assimilation in words like "bets" and "beds"; the difference between "putting up" and "putting out"; why it's (sometimes) okay to say "Hey fucker" to your best friend, but not to your teacher; and the deletion of nominative arguments in subjunctive phrases.
Second language learners often (maybe always) find more rules useful, for several reasons. However, those who learn the language in highly rule-focused manner often have difficulty actually communicating in the same way that Computer Science professors are sometimes quite knowledgeable about CS theory, but unable to produce good code. Rules are good at telling you what not to do, but bad at helping you be creative.
Yeah, native speakers won't typically be exposed to the same rules, and there aren't a lot of rules taught, but they are there to an extent.
I wouldn't say that one should learn in a rule-focused manner, but neither should one learn completely by example. A mix is best, even when your goal is to have the rules fall away in the end.
The new eastern span of the Bay Bridge is a similar example. They had to build a complete temporary bridge of iron girders to support the new roadway before the tower and cables were in place. (The bridge design didn't allow the tower and cables to be built first and then the roadway suspended like a conventional suspension bridge.)
This page has a good video of the combined structure and the process of shifting the roadway load from the temporary bridge to the cables:
After having lived 4+ years in Germany and struggling to learn German, I would say that the only way you can learn truly by pure immersion is from your parents. In any other case you need at least some theoretical basis because no one else is willing to spend hours trying to communicate with someone who's basically babbling.
I'm using Duolingo now and after I'm finished with it I want to get some formal classes to (hopefully) get to a B1 level. I wouldn't call Duolingo immersion learning though -- they explicitly provide grammatical rules (unless you're using the mobile app which lacks some features) and it's very difficult and frustrating to try to do it with your intuition alone.
In the language tutorials I wrote, I decided to write a whole section for people who didn't want to learn grammar. (http://langintro.com/kintro/grammar/hategram.htm) My example was Russian adjectives, where a 3 by 5 chart reduces to a 5-entry table plus two spelling rules.
I've been teaching a beginner's guitar class at the office with another coworker. Teaching to adults is interesting because as a kid I was satisfied without necessarily knowing the underlying foundational concepts of music (something that held back my development for a while) but adult students are quick to ask questions and dive deeper. "What do you mean play a minor chord?" is easy to explain away to a child and get the to accept an intuitive definition (to be explained more thoroughly later) but totally throws off adults who are used to having acquired deep knowledge in some other field.
As with music, math, programming, one does need a deep foundation to be good but also one needs to develop a feel by repeated effort so that your mind begins to recognize patterns.
As a kid I refused to learn music because no-one could give me a good explanation of the difference between the black piano keys and the white keys. The explanations were always circular: white notes are special because they are in C-Major; C-Major is special because it contains all the white notes.
(The correct answer is that people's hands aren't wide enough to deal with all twelve notes on the same level, and that particular subset of the notes contains a lot of consonant intervals and barely any dissonant ones.)
>As a kid I refused to learn music because no-one could give me a good explanation of the difference between the black piano keys and the white keys.
Doesn't that seem really stupid to you now or do you still support that stance? Refusing to learn the entire field of music because of one irrelevant detail is pretty appalling.
It makes you distrust the people teaching you - if they're going to answer your legitimate question with circular logic, it shows that they're missing some info and not willing to admit it. So they're either lying or wrong about this thing, and who know what else they're lying or wrong about?
Similar logic puts some people off of Christianity - x is in the Bible, and we know the Bible is true because the Bible says it is true, therefore x is also true. Hmm. Someone who tries to sell you that logic is also either lying or wrong, now you can't trust either that person or the Bible.
Imagine people had refused to use the calculus because no one could really answer what an infinitesimal value really was.
Sometimes you just need to make progress.
My understanding is that it was rejected by many mathematicians for precisely that reason, but that many others took up the challenge to answer the question rigorously, resulting in some major leaps in theory. On the other hand, it's good that many others were able to overlook the issue of the infinitesimals and put the techniques to lots of practical use. The lesson I take from this is that both first principles questioning and suspension of disbelief can be valuable tools for learning and discovery.
I don't think the GP (Kluny) or GGP (OscarCunningham) disagree with you on that point. If I understand them correctly, it's fine to have unresolved mysteries in your understanding, so long as you are honest about it and explicitly label it[1]. In this case, "hey, we can't quite put infinitesimals on a solid grounding (or Dirac Delta, or whatever), but it doesn't break anything else, so let's see if we can figure it out some other time."
There's a huge difference between "it's not worth our time to resolve this now" and "non-rigorous thought is okay, reality doesn't have to make sense, just do what the high-status people say, they're smarter".
[1] There's a practice in some groups to explicitly say "it works by magic" to avoid false understandings and to flag unresolved issues.
"If I understand them correctly, it's fine to have unresolved mysteries in your understanding, so long as you are honest about it and explicitly label it[1]."
Grit is hard to come by for kids. You never find yourself interested in 'the whole field of music'. You find yourself drawn to the immediate. Seeing a piano in front of you, you might want to learn about it. You might get turned off the exact same way.
Unless your parents are directing you, childhood is a random walk through the universe of creative possibility.
I think it's more of a rejection of the instruction, not the concept being instructed.
I had a similar experience with music instruction, everyone taught to the instrument and to the book of music, never any concepts of music theory even to the point of "What's with the sharps and flats over here by the squiggle? Why not put them where I can see them easier?" "Yeah, I don't know, it's kind of a pain, I just write them back in with pencil." "How do you write a new song?" "Oh, it's really hard, you have to be really smart like Beethoven. Don't worry about that, we have plenty of stuff to practice in the book."
Later, in self educating, I discovered key signatures, playing to those keys (and even improvising!), and that I don't have to think about sharps and flats except for accidentals and it makes so much goddamn sense, but no adult I had access to in childhood ever knew or at least none could explain something which was so fundamental, something that actually made music fun and allowed me to create a positive-feedback loop required for consistent practice.
Had I stood firmer on the grandparent's question, rejected instruction sooner (instead of just through confused burn-out), and begun to self educate sooner, I could have avoided wasting a lot of time.
A good teacher can get all of this for you. I knew all of that stuff because my mother was a violin teacher and she new musical theory in and out. Some of her first lessons are in theory before you get to sight reading so you don't have any questions like that. You had shitty teachers it sounds like and you should never reject formal education just because you had 1 bad experience.
It's funny, I "learned" piano for years as a child, but somehow missed a lot of the theory (e.g. the circle of fifths). A year ago, I got a deal on guitar lessons from a student who was looking for work for the summer. It was a crash course, pretty much taught the basic cords (G, C, D, Em, Am, etc) but we didn't have enough time to go into much theory there either. But it was enough of a crash course to start looking at the guitar and figuring out how it works, relative to my base knowledge on piano.
My partner is quite musical though (formally trained), and she's help fill in a lot of the gaps. I'm at the point now where I can fiddle around with different chord progressions and get good-sounding melodies to come out on my own. I get inversions and how they work on the guitar, etc. It's quite cool and way more interesting to me than just learning songs from a book.
Organ keyboards originally had only the long keys (the white keys) because they only had the natural notes of the scale. The accidentals were added later as the short keys, and were added as short keys so you could still play as though they weren't there.
Piano keys are the same because they copied the keyboard from the harpsichord, which copied it from the organ.
The reason the long keys are in C is because a piano is naturally tuned to C. Tighten all the strings a bit to bring it up to D, and all the long keys will be in the key of D.
it's defined somewhat arbitrarily but those 7 notes are the notes of the C Major scale. If you just pay them in sequence, that is the scale. Western music is based around 12 tones, but each scale only has 7 of those tones. A piano with black keys allows you to play in any key/scale (based around semitones) since all 12 tones are present but only 7 constitute the major scale.
By the "natural notes" I just mean the notes that would make up an octave in that key, like "Do, Re, Mi, Fa, Sol, La, Ti, Do" in whatever key you like. On a piano, the long (white) keys are tuned to C for that. If you start on a D and just play the white notes up, it won't sound right.
If you're asking "why is it tuned to C", it's probably because C is the key that historically was assigned the letters without any sharps or flats. There's no physical reason for this, it's just a convention (as opposed to, say, octaves, where each octave is half the frequency of the previous).
If you're asking why C got the letters without sharps or flats, I believe you have the Romans to blame for that. They did start with A for their scale without sharps or flats, but it was what we would now call "A minor". Which leaves C as the major scale.
Thanks for the comment, totally agree with moderation. My goal is to ask "Is the structure I'm providing helpful right now?".
There's an implicit assumption that "more structure is better" (especially in technical subjects that can be structured) because it seems official and defensible. It reminds me of many Wikipedia articles -- they grow in length (why not?) and become more precise (why not?) and you're left with a description inscrutable to a beginner.
Calculus, for example, gets my goat because we spend weeks on limits, continuity, L'Hospital's Rule, etc. so students can "properly" understand derivatives. (Never mind that Newton and Leibniz never used them and seemed to do ok.) Showing a circle non-rigorously transform into a triangle to measure its area (Archimedes) gets closer to the meaning of Calculus than a page of epsilons, deltas and tangent lines. One you have the idea, you put in the rigorous skeleton by showing how the formal rules describe the same result.
I also agree that you need a mix for optimal learning. I noticed myself that when trying to really grok something, most of the work happens after I both know the formal description and the intuitive idea behind it - it's figuring out how exactly the two fit together that leads to actual understanding.
Exactly. Terry Tao calls this having a "post-rigorous" understanding (https://terrytao.wordpress.com/career-advice/there’s-more-to...). We can't think the formal rules are sufficient. (And in the case of adjectives, it seems explicit knowledge of the formal rules aren't even necessary for fluency.)
My best math classes have been where the professor took the intuitive approach but prefaced it with a rigorous definitions so I always had a safety net to fall back on.
I went to school here in the UK, getting good marks in English and I have never heard of the Royal Order of Adjectives. It sounds like some official lackey the Queen might call on when she just can't find the right word.
I remember our English teacher giving us one single lesson on conjugation, and that was only because we were so confused by all the stuff about conjugating verbs in French class. Other than that I cannot remember us going near any kind of formal grammar.
edit - I just thought, it is also not that hard to construct a context in English where 'old little lady' can work.
I looked again at the little lady sitting across from me. At first, from her height, I had assumed her to be young. However now, looking closer, I could see she was a very old little lady indeed.
Precisely - you're not arguing against the article at all here. The point of this piece is that it is possible to learn how to do something without ever being exposed to the underlying rules. Or even to the fact that such rules exist.
Calculus, by comparison, is built on firm rules about what you are allowed to do and what you can't, when cutting a shape up into pieces and rearranging them. The piece is arguing that it might be possible to make headway in calculus by just being exposed to usage, and the formal rules can be kept to later. That seems quite compelling.
Precisely - you're not arguing against the article at all here.
Yep, I should have probably made that clear. Was more side commenting through the metaphor. In general, learning English like that works quite well, but then it throws you when you are then asked to conjugate the verb 'to be' in French class and nobody has ever asked you to ever conjugate a verb in English. You end up knowing how to use English, but do not learn the technical terminology required to dissect it.
>> we developed an ear for the language and know how it should sound. And “old little lady” sounds off
Until you get into regional dialects and slang.
It only sounds off if you are accustomed to reading correct English. I do a lot of reading, and I think that is what developed my ear for phrases which are 'incorrect'.
I can't tell you what a participle or things like that are because I haven't been formally trained, but I can tell you which sentence from a list is the correct one.
I hear some people talk and I'll shake my head as I hear them slaughter the English language, but then I realize they probably don't do a lot of reading and didn't get far and school and that's just how their peers talk, as incorrect as it may be.
there is no correct or incorrect way of talking. slaughtering the English language? as long as both people understand, it does not really matter.
language is not something that's set in stone - it constantly changes. I would encourage you to be curios and try to learn something from others ways of speaking.
Something not matching your expectations / what is commonly seen as the 'right' way does not make it wrong.
IMHO judging people that don't read or didn't get far in school is plain wrong.
In my experience, getting good at math requires first that you accept that your intuitions suck. Your natural intuition will constantly lead you astray mathematically. People who struggle with algebra are often people who are trusting their intuitions about what is correct. Eventually, you internalize the rules and they become your intuition. But to suggest that we should skip the rules and instead try to build up intuition seems rather wrong-headed to me.
>But to suggest that we should skip the rules and instead try to build up intuition seems rather wrong-headed to me.
The problem with natural languages, and especially english, is that there aren't really any formal rules as there are in well-defined maths like algebras.
You won't be able to complete a single formal, rigorous proof without clear, formal unambiguous rules. Yes, first principle reasoning is straining, requires hard work and causes headaches, but the understanding will be deeper and complete. The English language is shaped by use and constantly changing. Mathematics is not supposed to change unless we have a mistake in our axioms.
Consider imaginary numbers, which don't invalidate anything as such and have to be tidied away after you're done playing with them, but make an entire class of calculations much easier by providing a consistent way to deal with otherwise awkward problems.
They don't change the existing parts of the language, they just enlarge its body. Imaginary numbers don't invalidate the other rules. In natural languages, if you learn the rules down to the last nit-picky detail, you will soon realize that it is no longer valid, sometimes within years, other times within decades.
"Which little lady are you referring to? The old little lady, or the young "little lady" that is her five-year-old great granddaughter?"
Though order is a syntactic feature, the restrictions on adjective order are derived from semantics, which depend on context. They are not ruled out by the grammar, per se.
Therefore the rule which says it must be "little old lady" is plain wrong.
The fallacy consists of regarding incorrect or incomplete rules as the unvarnished truth which to learn from and imitate.
In "little old lady", "little" applies to "old lady", not "lady" alone.
Either way, the meaning is the same, because semantically, the actual attributes which "old" and "little" denote apply independently to the person indicated by "lady".
I'm a native English speaker, and I never came across such a thing. Often, such adjective mistakes are simply corrected because 'it sounds funny'. I took advanced courses in English and school, and as a weird result, missed out on much of the sentence labeling and other such things.
I'm also learning a language. I moved to Norway a couple years ago and am in the second year of classes. Rules, even when they are loose, help a lot as an adult learner because the rules give me something to lean on to make guesses. I'm just now starting to get a feel for what 'sounds' right, but thanks to the rules, I can bypass that for now and use the language skills I have and make do.
This same effect occurs in computer science with "big-O notation"
Every time I'm asked about big-O in a job interview, I'm asked to recite the formal rules of the notation, rather than demonstrate how to use the resulting insight to make the code better. Just because I don't know the formal rules of how to calculate Big-O they assume I can't write any code that scales.
Its like a teacher assuming a student can't speak english because he can't recite the adjective order chart from memory.
Yep. I don't deny that academic success is correlated with real-world success, but assuming that they're identical is a terrible mistake. Especially now given how hard it is to hire good developers, I think Mensa-puzzle interviews and CS-exam interviews are terribly wasteful.
In Isaac Asimov's biography he mentions taking some intelligence test (perhaps in the Army?) that checked for familiarity with advertising slogans. Sure, there was probably a correlation there, but know we realize that's fundamentally dumb.
Since big-O and other asymptotic notations come from calculus I don't think it is a bad idea to know precise definition. For programmers it is questionable how useful they are in everyday job and I would just forgo asking them during interviews, although I have been asked in recent interviews. These asymptotic notations are immensely helpful in finite approximation of continuous functions using infinite series like Taylor series or orthogonal polynomials. Computer scientists borrowed the notations and abused them as if they were the final arbitrator of things when they are not; Knuth noted too much game is being played with them in academic publication. Further attempts at drawing analogies different kinds of convergence and growth functions have not found widespread use.
I guess I am saying don't underestimate the importance of rigor in knowing precise definition of mathematical notations.
Wow, I have never interviewed at a company that asked for formal rules of big-O. And of course most professionals at those same companies (you've heard of them) tend to use "O()" to mean "approximately" or "on the order of", as in "O(1000)"
I don't think it's necessary to know the formal definition of big O (or big Theta or big Omega) but there's a spectrum there. If all you can say is "nested for loops are bad" and you can't explain why hash tables provide fast lookups then I'm not going to be very impressed.
On the other hand plenty of people can memorize that a lookup in a BST is O(log n) without understanding what that actually means. If you can explain that a balanced BST grows in height by powers of two without actually using the phrase "log n" then that's more impressive than the person who does rote memorization without understanding what it actually means.
I'm going to render myself permanently unemployable in the industry by admitting this, but one thing I'm still not really sure about is why every text on CS assumes array have O(1) access? I mean, in the real world it surely takes more time to reach elements further in memory, if only because electrons travel at finite speeds and also you can't magically write any number into a register, there has to be a piece of electronics that will count up to it somehow. Is it only because all those hardware operations are so stupidly fast we don't care about them day-to-day usage, or is there another reason for assuming arrays have O(1) access?
My understanding from my algorithms class is that it is simply a matter of choosing your abstraction. Big O is meant to provide a general framework for qualifying and comparing algorithms free of machine dependent factors like execution time. It is not possible to account for every possible facet of every operation so some operations are chosen to be O(1) even though in reality they take multiple machine code instructions or have slightly varying real world performance. Saying array access is O(1) also does not account for different architectures or cache misses, which have major performance implications.
So in the case of arrays, since we do not need to read A[0] and A[1] to access A[2], it makes more sense to say it is an O(1) operation.
Another example is arithmetic. Addition and multiplication are considered O(1) operations for many algorithms even though multiplication is slower than addition. At a lower level, addition could be considered O(log n), since the binary representation of numbers has O(log n) bits of input. But the abstraction of addition as an O(1) operation is more useful at a higher level.
Also in Big-O, we drop everything but the major term, so accessing element 0 may be O(1.0001) while accessing element 20 is O(1.0003), they are both still considered O(1).
This is purely my takeaway from my undergrad algorithms class, so it may not be entirely accurate. Please correct me if I am wrong or misleading.
First, no, in the real world it does not take more time to reach elements further in memory. Even if the memory is physically further on a chip (and some memory has to be), the memory transfer happens on a clock edge, not just "as soon as possible", so the elements actually transfer at the same time.
On to the larger point: O(1) does not mean "twice as fast as O(2)". It means "does not take longer depending on how many elements there are". That is, if I have an algorithm that takes twice as long as an O(1) algorithm, the slower algorithm is still O(1). We do not care about constant factors when dealing with big-O notation.
Accessing an array is O(1). What do you have to do to access an array element? You have to take the size of an array element, and multiply it by the index of the element, and add the starting address of the array, and access the memory at that address. That's O(1), because it does not depend on the number of elements in the array.
In contrast, accessing an element in a linked list is O(N). You have to start at the beginning of the list, and keep getting the next element until you get to the one you want. On average, that takes N/2 operations for a list of N elements. But we don't care about constant factors like 1/2 in big-O notation, so accessing an element of a list is O(N).
But if I want to insert an element into the middle of a linked list, and I already have a pointer to the place where I want to insert it, that insertion is only O(1). I have to change swap some pointers around (2 or 4, depending on whether it's a singly- or doubly-linked list). But that doesn't depend on the size of the list. Whereas if I want to insert an element into the middle of an array, I have to move all the elements after the inserted item, which is an average of N/2 items, which means that operation is O(N).
This is a completely inadequate explanation of big-O, but I hope it's enough to clear things up at least a bit for you...
> Even if the memory is physically further on a chip (and some memory has to be), the memory transfer happens on a clock edge, not just "as soon as possible", so the elements actually transfer at the same time.
Here is the key insight I was missing. Thank you very much!
Constant time means the time, expressed in the number of steps the algorithm takes, doesn't vary based on the size of the input. The time to reach the relevant memory doesn't vary on the size of the input, but rather on the topology of your architecture. Further elements may well take less time, depending on where they're actually stored, so you can simply average out memory access to get a constant factor.
Now, if the number of times you had to access the memory in order to retrieve the data in the array depended on how big the array was, then you'd have O(N). An array is specifically designed so you only have to go to memory twice, first to get the memory address stored at X position in the array, then to retrieve the information stored on that position.
A linked list, as described in a sibling comment, actually does have to do this. You trade easy accessibility for other properties.
Ditto for the steps to do register operations and any of the other machine language instructions. The time can vary, but not as a function of the size of the input. So it's still constant time.
It takes longer to access elements that aren't in cache, but that's still a constant factor. It may be 100x or 1000x but once you're going all the way to main memory it's not going to get any worse as your array gets bigger.
I say the same thing about hashtable lookup. See this thread and the linked Reddit one[1].
To answer your immediate question, the "general computation model" assumes constant memory access time. It's hand-wavy, but at least it's consistent.
The bigger problem is that for hashtables, even under ideal, non-physical assumptions, you still can't logically derive O(1), because there are unavoidable, inherent computations you have to do as the hashtable gets arbitrarily large. Either you a) adapt the hash function to have a bigger output, or b) you allow values to stack up in each output slot. a) is log(n), b) is n.
I don't know anyone who could read the hashtable implementation, without knowing the "right" answer, who would reasonably say "oh, that's O(1), obviously".
Thanks very, very much for pointing me in the right direction! In the thread you linked, 'Cushman links[0] to a good StackExchange thread[1] that explains some related things that bothered me, and the whole thread also manages to answer my questions regarding arrays.
I wondered about hashtables too. I was actually teaching someone about them recently and had to re-read some CS stuff for it, and in the process I realized that the O(1) access for hashtables doesn't make any sense in the light of explanations I know.
So it turns out that the answer is complicated and in CS curriculum they just handwave you through. It sucks, to be honest, and it's the one thing that always annoyed me about formal education - far too often the teacher/professor stated something as a fact and provided a "proof" with so much confidence that I sort-of assumed it must be so, and realized only months or years later (and after a lot of confusion) that I learned an approximation - maybe a smart one, with good reasons backing it up, but still just an approximation, with important caveats that were never even mentions.
It sorts of make you wonder how much do you really understand about things, even in STEM.
I think there's a subtlety you might be missing, correct me if I'm wrong.
I stated in my first reply that the growth rate is notated as a function of the size of the input. Big O is itself an approximation, you don't use it if you absolutely have to know all the other factors that don't vary on the size of the input. Such as if they vary on your memory architecture. In practice they tend not to matter, Big-O is sufficient for most purposes.
If you do need the detail, you remove the Big-O and write out your other factors so you can compare them to other algorithms at the right level of detail. There are also other notations you can use that convey other concepts, such as little-o, little-theta, big-theta. When you use a Landau symbol[1], as these are called, you're making an approximate statement by definition.
It's still perfectly fine to call array access O(1), even if your data is stored on Pluto, and it's Odysseus doing a space opera Odyssey for each retrieval, you're still only going there twice. Even if there are sub-algorithms that you are calling within the main one, you're still only calling them a constant number of times. If the first time you go to Pluto to get data it takes 6 months and the second time it takes 30 years, because of complications, it's still constant time.
If you were accessing a linked list stored on Pluto, then you're going to Pluto a number of times depending on how deep in the linked list your data is, assuming it's a dumb probe and it can't figure out where to go once it gets to Pluto and has to come back to earth to figure out what to do next. (go back to Pluto)
If it turns out retrieval time matters, or other factors besides the size of the input, then you can't approximate over them and Big-O ceases to be useful.
If you assume the usual primitives (memory, arithmetic) are O(1), can't you still get an amoratized, expected performance of hashtables.
Given O(1) arithmatic, you should be able to use an O(1) hash function. At that point, you only have to deal with realocation as your tables grows without bound. You can solve that problem by using the 2n allocation method that gives us O(1) amortized appending to vectors.
Of course, you still need to make messy assumptions about randomness.
Any bounded size hash function has a bounded size output, which means a bounded number of buckets (number of possible outputs). That means that as the hash table gets arbitrarily large, you have to keep stacking new elements in each bucket. As the size goes to infinity, each bucket has a linear number of elements which have to be accessed in linear time.
You don't: that's the other alternative. But if you allow the hash table to resize as you increase the hash function (that is, adapt the function to one that has a larger output), then that's still not constant with respect to the table size. Computing a larger output requires logarithmically more operations to compute the hash, assuming you use one with the same well-mixedness properties.
A hash function with 5 bits of output needs more operations than one with 2 bits of output.
Thanks everyone for chiming in and taking time to write your answers! I did know the general concepts behind O-notation, but no doubt I now understand it even better :).
Just as in math there is an applied and theoretical aspect, there is in CS as well. There are plenty of great opportunities to us calculus in stat, econ, physics and so on, but calculus can be a great introduction to proof writing itself.
In the same vein algorithmic complexity can be a fantastic first gentle introduction to theory and it's best when tied into writing algorithms in a data structures class. The same can be said about regexps for example - practical v theoretical aspects - or logic as applied with prolog (or even make) say.
The interesting thing (as seen in a comment below about arrays and constant big-O) is that often intuition goes against the the rigorous understanding - so it's best to have both. I suspect the same holds for language as well. For example etymology of word roots as well as actual writing using the words.
Terrific article. And it turns out the complex adjective chart isn't even sufficient to capture the rules. Apparently there are exceptions and it's an area of continuing research:
There shouldn't even be formal rules. The meaning of linguistic constructs are determined by how the appropriateness of phrasing is captured by usage in context. Whether "old little lady" or "little old lady" is correct is largely a matter of what you are more comfortable with, which is a matter of how people around you spoke when you learned the language.
Formalizing it would be about as silly as formalizing which music sounds good.
No, what I mean is that the rules are only at best heuristics for mimicking another style of writing. They're not correct or incorrect, except so far as they are poor representations of some specific culture.
To say there are formal rules of language is a bit like saying there's only one culture that is fit to judge the acceptability of your words.
Yeah, any time I see something like this I think, it would only take a couple of widely read books or widely watched TV shows breaking these "rules" to change what "sounds right" to a lot of people. Having said that, studying the evolution of these sorts of idioms over time seems fascinating to me.
Sorry, I think that's complete bullshit. And there is indeed a great deal of theory that formalizes what makes music sound good; most of it is maintaining patterns of whole-number ratios to derive scalar and rhythmic intervals, and there are certain algorithms and formal rule systems that reliably produce pleasing results within particular genres. Even music that deliberately breaks these rules (like 'noise music' involving extreme distortions or recordings of 'unmusical' sounds) can be thought as a meta-development of those rules; the equipment or source material employed to make such 'unmusical' sounds acts as constraints, and lead to emergent structures of their own.
Well, I don't wish to get in a fight and I'm sorry if my blunt response came across as a personal attack. I'll try to keep a more open mind and work harder at understanding your perspective rather than just restating my own.
I think you're confusing linguists with usage mavens. This type of research isn't prescriptive -- it's descriptive. The "rules" are attempts to describe how people actually use English, in a variety of contexts. If common usage changes, the rules would change.
Saying the rules shouldn't exist is like saying Newton's laws shouldn't exist -- they are just patterns that someone has noticed.
While there seem to be exceptions to most rules proposed (because natural usage is complex), the rules are still fairly accurate for most cases.
The primary use of these rules, in my experience, is to prevent the common usage from changing. You certainly don't do a good job teaching language by asking people to memorize formal rules. You also aren't going to make a computer understand natural language by writing down formal rules.
So why do it? To make observations? Observations don't need formalization; just provide good statistics.
I teach music lessons professionally and spend hours every day playing with this exact concept. To me it's really about building off of what a student already 1) knows conceptually (rules) and 2) has experienced (intuition).
What I've learned is that you can't teach any type of rule until all it's "prerequisite phenomena" has been experienced. Music education has a bias of more "doing" and experiencing and less "talking" about (or it should at least). So it has a keen way of turning ideas and concepts into action rather quickly. I think many other disciplines in school can learn a bit from how music is taught frankly: there is a very quick turnaround from concept to application/experience and therefore to emotional context of some sort, which really is the end goal to all learning. Why do you care about X?
So if a rule simply is an equation of some sort, or a statement of relationships, then the prerequisite phenomena is making sure every variable is defined within it; so that one can focus solely on the relationships within the objects instead of the undefined variables. This covers many different grounds depending on the style of the learner and the material at hand. Sometimes (rarely) words are enough (if you're building familiar rules into new rules and the experiential phenomena is all done in the mind "ah-ha!") and usually, a student needs to hear the sound of a major scale vs a minor scale and try to describe it with words before telling them what actually makes it sound different theoretically. And even then, there are different ways to explain it. If the student picked up major scales really well (prerequisite phenomena), I will use the modal approach to learning minor scales (it's the major scale but starting from a different note), if the student picks up the scale tones and is better with spacial relationships, they usually already talk about the differences between what they just played as a sharp/flat 6th or 7th scale tone. And there you have it, they've just instructed YOU how they think about a concept.
Music is a great example of how there is no single correct way to explain the theory. First off, music practice and artistic decisions always came first, the theory came later as people tried to understand and teach it. And it is the bias of educators to find a single correct way to understand it within themselves that leads to them only prescribing one way to do something (memorize this!). Teaching really is listening more than it is speaking.
Interesting article, and it does describe things that we should strive for---an intuitive sense is a key sign of mastery of a subject. However, the idea that we should learn math the way we learn languages has a flawed premise. Human beings have been equipped by evolution with the capacity to acquire language by exposure. Cognitively normal children aquire language, including the complexities of grammar, through simple exposure to people speaking that language during a particular period in their development. It's unfortunate that this ability doesn't persist through life, or apply to more than one language for most people. But for children, language acquisition is completely effortless.
This is not the case for other cognitive skills, such as reading and (to our point) mathematics. My son cannot learn calculus simply by hanging out in my office. While our end goal may be the sort of effortless intuition in mathematics that we experience in parsing complicated sentences, the process of acquiring those two skills is of necessity widely divergent.
Why does the phrase "old lady" or "little old lady" pop into your head when you go to speak about an old lady? Because you have heard the phrase many times before.
It's just memory, we recite timeworn phrases because that's what we hear over and over.
Non-native speakers use phrases that "sound wrong" only because they are synthesizing from principle or from their own language, and haven't heard the usual phrases over and over.
This is where rule-based language analysis runs aground.
Okay, but let's assume you encounter a goat. It is purple. It is from Mexico. It is tiny. It seems to also be a robot. I'm guessing you've never come across someone describing such a thing to you before, such that you can identify from memory the correct way to describe that goat.
So why, when someone shouts out "Look out for that robot purple tiny Mexican goat!" you would immediately peg them as not a native English speaker, but if they had said "Look out for that tiny purple Mexican robot goat!" you would not?
This is not a 'fixed phrase' thing. There are rules, you're just not consciously aware of them.
Maybe I was incredibly lucky, but whenever someone rails against how awful the "standard" math education is, and recommends a "better way", I note that the "better way" was how I was taught.
I suspect what happens is that students forget some of the good basic ideas (or is that "basic good ideas" ;-) ) they were taught, and teachers fail to re-emphasize them to keep students on track, and so all they remember is the formal/abstract techniques they spent a login time struggling with. Painful experiences stick in our memort more than smooth easy experiences.
Focusing only, or mostly, on formal structure always[0] seemed to me to be just a failure of teacher at introspection. For instance when using your native language, if you stop and look at your own thought process, you'll quickly realize that you don't consciously invoke any grammar rules. In fact, the brain doesn't have enough computing power to explicitly build sentences by applying grammar rules, not if you want to have a conversation. It should be obvious, on introspection, that formal structure can be only a scaffolding for building your cache.
[0] - For things you learn to use all the time, or to leverage your cognitive process. The obvious exceptions are things you want to do with mindless precision, where the risk of guessing wrong is unacceptable. Compare public speaking to memorizing a poem, or guesstimating to doing explicit pen and paper arithmetics.
ROA: this is the first time I've ever heard of such a thing. I'm not surprised such a thing exists, but as a native speaker who has done a whole lot of writing I find it amusing I've made it for so long without ever encountering the attempts to formalize it.
In my third semester of Calculus class, I had a Physics professor. True to his background, he would sometimes take the entire class elaborately explaining the geometric interpretation of complex 3D operations, something I greatly appreciated. The formal notation and theory was always there, but he made sure the intuition was there also (if possible). Best math teacher I've ever had.
I had a slightly weird schedule, and didn't end up taking E&M until way after I had finished all four semesters of Calculus. I walked out of the Calculus series being able to turn the crank quite well, but I didn't have a very good feel for what it meant. E&M made all the difference!
In high school our physics professor (and an actual physics PhD) decided that he can't teach us "real physics" without derivatives and integrals (the latter not being in high school curriculum at all), so by the end of the first year, he taught as both. Our maths teacher started tearing her hair out over this, complaining about lack of rigour; eventually she gave up and taught us integrals with full mathematical formality. Having those two takes on the topic helped us understand it really well.
Another science class anecdote - first year electronic engineering, the professor is showing us the derivation of transistor gain formula. He started from pretty much first principles, written out a huge formula, and then started to cross things out - "this in practice is close to 1 so we can ignore it", "in standard operating conditions this is pretty much zero" (and poof, half of the equation gone, multiplied by zero) - and kept going until he arrived at the standard I_c = βI_b. It gave me a new appreciation of just how much engineering is basically handwaving parts of reality away.
We didn’t become good at English by studying a chart: we developed an ear for the language and know how it should sound.
Unless we grew up speaking a different language, or were born to people who didn't have English as their first language. My wife has been in the US since the age of 2 and speaks perfectly but she still has a few minor linguistic tics that a second-generation native speaker wouldn't, and is she shy if she comes across a word she's not sure how to pronounce or whose meaning is unclear.
Having taught English as a second language to people from a wide variety of backgrounds, I don't expect anyone to memorize the royal order of adjectives, but it's incredibly useful for them to know that there is an underlying system and to match patterns of adjectives from their reading material against it, or play games with it (like thinking deliberately wrong phrases such as 'old little lady' for comic value), or be able to refer to it if they're nervous about writing something. The same is true for people who miss out on a proper education because of domestic or socioeconomic problems and maybe come to literacy as adults, but never develop the total confidence of someone surrounded by language since birth. Incidentally, those of you who live in California may have noticed the public information campaign encouraging parents to talk and sing to children, especially babies and toddlers. Research indicates that this has a massive influence on brain development and subsequent success or failure in life. See http://www.economist.com/news/science-and-technology/2159692... for an overview.
So yeah, of course the best way to acquire language is to be in a linguistically rich environment, and just soak it up to develop an intuitive understanding that promotes linguistic creativity and wordplay, as opposed to studying it through formal methods and turning it into a philological exercise. But that does not mean that formalism is bad, or that we should conceal the existence of systematic structures from kids in case it will wreck their creativity or something - if for no other reason, than to spare them the waste of reinventing the wheel should they be inclined to adopt a formalist approach on their own initiative. It's very easy to handwave away such rigid-seeming pedagogical tools if you already enjoy the benefits of total fluency, but for those who do not enjoy the same advantages this is the equivalent of pulling up the ladder behind oneself and then critique the confused for poor listening skills.
I don't have a comment on the math part - I agree with the author that we ought to be open to using multiple learning techniques so that each student can find the best one, but I think he seriously underestimates the utility of formality. When I was 5 I thought chanting multiplication tables every day at school was a bit silly, but 40 years later I greatly appreciate the fact that I can handle everyday trivial math problems reflexively rather than needing to reach for a calculator, pencil and paper, or a mental script of how to perform the calculation. Repetitive drills and formal methods are not the best way to explain new concepts, but they are incredibly useful exercises to retain them and make the basic knowledge feel instinctive in later years.
It bugs me that he doesn't actually give a reason for why these orderings are "right", beyond his having an intuition for them (which might be just pattern learning, as others here mention).
It's been said (citation needed) that phrases like "tick tock" and "see saw" are in those orders because it's a high or hard vowel before the low or soft (e.g. "tock tick" sounds weird). Maybe that is why "little old" lady sounds more correct to us? I don't know. But the article goes off to draw a parallel to mathematical intuition, and leaves the original grammar problem unresolved, in my opinion.
Incidentally, I usually _really_ like the Better Explained articles.
Thanks for the feedback! Glad you've enjoyed the articles thus far :).
The adjective order rules are interesting in that we have to reverse-engineer them from our brains, but aren't consciously aware of them. It's apparently an area of ongoing research why certain orderings are correct. (Maybe there's something about the specificity of the adjective, where the more-specific items are closest to the subject.)
I think the higher-level concern is we can get tricked by thinking we need to consciously master the structure in order to be fluent, vs. letting our brain's pattern-matching skills do some of the heavy lifting.
Hey, appreciate your reply to my comment! And fair response, I'm glad to hear from scientists that are able to talk about open research, as opposed to trying to make a dogmatic point or conjecture without evidence.
I like the view that this is an open problem and an area of active research, much more than the more conventional, lay-person settling of the issue as "developed an ear for the language" and that's the end of it.
The impressive work of people like Steven Pinker and Chomsky (in his actual academic field) is to look very carefully at different ethnographic groups, and the larger cultures those groups are embedded in. By doing so, finding groups isolated enough or with a materially different context, such that they don't exhibit the same patterns.
The title of the article felt like a bait-and-switch, I guess. When I realized it was on betterexplained, it did make more sense that it was ultimately about mathematical reasoning. No worries!
Thanks for the reply. I struggled with the title a bit, in my head I think of the "XYZ Fallacy" as a trap we are likely fall into. For me, the trap was overemphasizing a set of implicit rules and trying to explicitly teach those rules to newcomers. (I.e., the newbies are required to use a structured approach that proficient practitioners never needed or even know about.) This is my personal lingo though, and might not make sense to others.
That's not the point - grammar doesn't have an underlying truth so there's no reason why one order is right and another isn't. The point is to give an example of how people are able to make progress in successfully using and understanding English without having any awareness of one underlying rule (people will even argue - as they do here in these comments - that there is no underlying rule, even though there certainly does seem to be, even though native speakers are generally never taught it).
That does make it different from mathematics, where there are reasons for the rules (you can't divide both sides of an equation by a value if that value might be zero, for example). But the point is more to suggest that it could be possible to make progress in carrying out and understanding mathematics without understanding some of the formal underlying rules beneath a concept. That seems like a valid point.
> Similarly, getting good at math doesn’t mean marching through a gauntlet of rules on every problem
No, it does to a degree. The rules are inferred from observation and internalized, but not precisely. "little" before "old" is a rule, almost motoric. As a foreign speaker I agree that isn't a logical rule :)
edit: I guess, the author is looking for the term heuristic (a general rule that is right often enough, but not precise nor complete).
This is actually sort of called out in the comments on the post, but I think it bears saying again in my own way.
It's deeply disingenuous to compare effortless biologically-determined learning to effortful general learning and think you can apply lessons from one to the other. Even in the example the OP picked, there's a reason that the learners drill the adjective order table, and it's because without the drill they will never learn it at all. Learning a language as a small child is a different process than learning the same language as a late teen or adult, and the results are very different. (Even so, I wouldn't bother instructing people in adjective order... if they do never learn it, it's no big loss.)
On a different, more technical note, OP doesn't quite understand what's going on in the example either. "Vietnamese spicy food" is perfectly standard English; the ordering there is determined by context. "Vietnamese spicy food" is a subset of spicy food, and will be used whenever it's being contrasted with other spicy food, whereas spicy Vietnamese food is a subset of Vietnamese food, and will be used whenever a contrast is drawn between spicy Vietnamese food and other Vietnamese food. (It's correct, however, that in the zero-context case, "spicy Vietnamese food" is preferred. In my analysis, that's more because people are likely to reify the concept of "Vietnamese food", which makes the phrase structure ("spicy" [adj] "Vietnamese food" [noun]) rather than ("spicy" [adj] "Vietnamese" [adj] "food" [noun]).)
Interestingly enough in the example he gave 303 x 13 I actually didn't look at the last digit to see that 5074 is wrong, I did an instant mental calculation of 300x13=3900 and saw that 5074 can't possibly be right before reading on.
110 comments
[ 3.4 ms ] story [ 186 ms ] threadBut in principle I agree with you. We need a bit of book learning to go with the "just start speaking" approach.
http://www.nthuleen.com/teach/grammar/adjektivendungenexpl.h...
I'm going to make a lame attempt to coin a term and call this the Arch Fallacy, which is when you look at your goal and assume anything not present in it is unnecessary to achieve it. A completed arch contains no supports within it, but you'll have a tough time building one without any.
Funny thing is on first reading, I didn't notice that at all and read it the way you meant. I only saw the typo on a second reading. Interesting autocorrect the brain does.
In any case I like your Arch Fallacy! I think I will use it.
I'll use it too, it's great and I don't recall any term for that particular error in thinking. I've already started spreading it (the name, not the error) among friends, hoping it will catch on.
Native speakers are taught some rules, but many are rarely taught unless a student has learning difficulties. The adjective ordering that OP mentions is a solid example. Others include aspiration of stops; voicing assimilation in words like "bets" and "beds"; the difference between "putting up" and "putting out"; why it's (sometimes) okay to say "Hey fucker" to your best friend, but not to your teacher; and the deletion of nominative arguments in subjunctive phrases.
Second language learners often (maybe always) find more rules useful, for several reasons. However, those who learn the language in highly rule-focused manner often have difficulty actually communicating in the same way that Computer Science professors are sometimes quite knowledgeable about CS theory, but unable to produce good code. Rules are good at telling you what not to do, but bad at helping you be creative.
I wouldn't say that one should learn in a rule-focused manner, but neither should one learn completely by example. A mix is best, even when your goal is to have the rules fall away in the end.
This page has a good video of the combined structure and the process of shifting the roadway load from the temporary bridge to the cables:
http://baybridgeinfo.org/projects/sas
The background image on the page is also nice, showing all three bridges together:
http://baybridgeinfo.org/sites/default/files/images/backgrou...
I'm using Duolingo now and after I'm finished with it I want to get some formal classes to (hopefully) get to a B1 level. I wouldn't call Duolingo immersion learning though -- they explicitly provide grammatical rules (unless you're using the mobile app which lacks some features) and it's very difficult and frustrating to try to do it with your intuition alone.
I also liked the explanation of cases and adjective endings from this site: http://yourdailygerman.com/learn-german-online-course/
As with music, math, programming, one does need a deep foundation to be good but also one needs to develop a feel by repeated effort so that your mind begins to recognize patterns.
(The correct answer is that people's hands aren't wide enough to deal with all twelve notes on the same level, and that particular subset of the notes contains a lot of consonant intervals and barely any dissonant ones.)
Doesn't that seem really stupid to you now or do you still support that stance? Refusing to learn the entire field of music because of one irrelevant detail is pretty appalling.
Similar logic puts some people off of Christianity - x is in the Bible, and we know the Bible is true because the Bible says it is true, therefore x is also true. Hmm. Someone who tries to sell you that logic is also either lying or wrong, now you can't trust either that person or the Bible.
There's a huge difference between "it's not worth our time to resolve this now" and "non-rigorous thought is okay, reality doesn't have to make sense, just do what the high-status people say, they're smarter".
[1] There's a practice in some groups to explicitly say "it works by magic" to avoid false understandings and to flag unresolved issues.
Yes, exactly.
Unless your parents are directing you, childhood is a random walk through the universe of creative possibility.
I had a similar experience with music instruction, everyone taught to the instrument and to the book of music, never any concepts of music theory even to the point of "What's with the sharps and flats over here by the squiggle? Why not put them where I can see them easier?" "Yeah, I don't know, it's kind of a pain, I just write them back in with pencil." "How do you write a new song?" "Oh, it's really hard, you have to be really smart like Beethoven. Don't worry about that, we have plenty of stuff to practice in the book."
Later, in self educating, I discovered key signatures, playing to those keys (and even improvising!), and that I don't have to think about sharps and flats except for accidentals and it makes so much goddamn sense, but no adult I had access to in childhood ever knew or at least none could explain something which was so fundamental, something that actually made music fun and allowed me to create a positive-feedback loop required for consistent practice.
Had I stood firmer on the grandparent's question, rejected instruction sooner (instead of just through confused burn-out), and begun to self educate sooner, I could have avoided wasting a lot of time.
My partner is quite musical though (formally trained), and she's help fill in a lot of the gaps. I'm at the point now where I can fiddle around with different chord progressions and get good-sounding melodies to come out on my own. I get inversions and how they work on the guitar, etc. It's quite cool and way more interesting to me than just learning songs from a book.
Organ keyboards originally had only the long keys (the white keys) because they only had the natural notes of the scale. The accidentals were added later as the short keys, and were added as short keys so you could still play as though they weren't there.
Piano keys are the same because they copied the keyboard from the harpsichord, which copied it from the organ.
The reason the long keys are in C is because a piano is naturally tuned to C. Tighten all the strings a bit to bring it up to D, and all the long keys will be in the key of D.
... briefly, before the piano implodes.
If you're asking "why is it tuned to C", it's probably because C is the key that historically was assigned the letters without any sharps or flats. There's no physical reason for this, it's just a convention (as opposed to, say, octaves, where each octave is half the frequency of the previous).
If you're asking why C got the letters without sharps or flats, I believe you have the Romans to blame for that. They did start with A for their scale without sharps or flats, but it was what we would now call "A minor". Which leaves C as the major scale.
Thanks for the comment, totally agree with moderation. My goal is to ask "Is the structure I'm providing helpful right now?".
There's an implicit assumption that "more structure is better" (especially in technical subjects that can be structured) because it seems official and defensible. It reminds me of many Wikipedia articles -- they grow in length (why not?) and become more precise (why not?) and you're left with a description inscrutable to a beginner.
Calculus, for example, gets my goat because we spend weeks on limits, continuity, L'Hospital's Rule, etc. so students can "properly" understand derivatives. (Never mind that Newton and Leibniz never used them and seemed to do ok.) Showing a circle non-rigorously transform into a triangle to measure its area (Archimedes) gets closer to the meaning of Calculus than a page of epsilons, deltas and tangent lines. One you have the idea, you put in the rigorous skeleton by showing how the formal rules describe the same result.
Appreciate the comment!
I remember our English teacher giving us one single lesson on conjugation, and that was only because we were so confused by all the stuff about conjugating verbs in French class. Other than that I cannot remember us going near any kind of formal grammar.
edit - I just thought, it is also not that hard to construct a context in English where 'old little lady' can work.
I looked again at the little lady sitting across from me. At first, from her height, I had assumed her to be young. However now, looking closer, I could see she was a very old little lady indeed.
Calculus, by comparison, is built on firm rules about what you are allowed to do and what you can't, when cutting a shape up into pieces and rearranging them. The piece is arguing that it might be possible to make headway in calculus by just being exposed to usage, and the formal rules can be kept to later. That seems quite compelling.
Yep, I should have probably made that clear. Was more side commenting through the metaphor. In general, learning English like that works quite well, but then it throws you when you are then asked to conjugate the verb 'to be' in French class and nobody has ever asked you to ever conjugate a verb in English. You end up knowing how to use English, but do not learn the technical terminology required to dissect it.
Until you get into regional dialects and slang.
It only sounds off if you are accustomed to reading correct English. I do a lot of reading, and I think that is what developed my ear for phrases which are 'incorrect'.
I can't tell you what a participle or things like that are because I haven't been formally trained, but I can tell you which sentence from a list is the correct one.
I hear some people talk and I'll shake my head as I hear them slaughter the English language, but then I realize they probably don't do a lot of reading and didn't get far and school and that's just how their peers talk, as incorrect as it may be.
language is not something that's set in stone - it constantly changes. I would encourage you to be curios and try to learn something from others ways of speaking.
Something not matching your expectations / what is commonly seen as the 'right' way does not make it wrong.
IMHO judging people that don't read or didn't get far in school is plain wrong.
The problem with natural languages, and especially english, is that there aren't really any formal rules as there are in well-defined maths like algebras.
If there are no rules, how can you skip them?
"Which little lady are you referring to? The old little lady, or the young "little lady" that is her five-year-old great granddaughter?"
Though order is a syntactic feature, the restrictions on adjective order are derived from semantics, which depend on context. They are not ruled out by the grammar, per se.
Therefore the rule which says it must be "little old lady" is plain wrong.
The fallacy consists of regarding incorrect or incomplete rules as the unvarnished truth which to learn from and imitate.
In "little old lady", "little" applies to "old lady", not "lady" alone.
Either way, the meaning is the same, because semantically, the actual attributes which "old" and "little" denote apply independently to the person indicated by "lady".
This is natural language. One contrived corner-case counter-example doesn't invalidate the general rule.
Every time I'm asked about big-O in a job interview, I'm asked to recite the formal rules of the notation, rather than demonstrate how to use the resulting insight to make the code better. Just because I don't know the formal rules of how to calculate Big-O they assume I can't write any code that scales.
Its like a teacher assuming a student can't speak english because he can't recite the adjective order chart from memory.
In Isaac Asimov's biography he mentions taking some intelligence test (perhaps in the Army?) that checked for familiarity with advertising slogans. Sure, there was probably a correlation there, but know we realize that's fundamentally dumb.
I guess I am saying don't underestimate the importance of rigor in knowing precise definition of mathematical notations.
On the other hand plenty of people can memorize that a lookup in a BST is O(log n) without understanding what that actually means. If you can explain that a balanced BST grows in height by powers of two without actually using the phrase "log n" then that's more impressive than the person who does rote memorization without understanding what it actually means.
So in the case of arrays, since we do not need to read A[0] and A[1] to access A[2], it makes more sense to say it is an O(1) operation.
Another example is arithmetic. Addition and multiplication are considered O(1) operations for many algorithms even though multiplication is slower than addition. At a lower level, addition could be considered O(log n), since the binary representation of numbers has O(log n) bits of input. But the abstraction of addition as an O(1) operation is more useful at a higher level.
Also in Big-O, we drop everything but the major term, so accessing element 0 may be O(1.0001) while accessing element 20 is O(1.0003), they are both still considered O(1).
This is purely my takeaway from my undergrad algorithms class, so it may not be entirely accurate. Please correct me if I am wrong or misleading.
On to the larger point: O(1) does not mean "twice as fast as O(2)". It means "does not take longer depending on how many elements there are". That is, if I have an algorithm that takes twice as long as an O(1) algorithm, the slower algorithm is still O(1). We do not care about constant factors when dealing with big-O notation.
Accessing an array is O(1). What do you have to do to access an array element? You have to take the size of an array element, and multiply it by the index of the element, and add the starting address of the array, and access the memory at that address. That's O(1), because it does not depend on the number of elements in the array.
In contrast, accessing an element in a linked list is O(N). You have to start at the beginning of the list, and keep getting the next element until you get to the one you want. On average, that takes N/2 operations for a list of N elements. But we don't care about constant factors like 1/2 in big-O notation, so accessing an element of a list is O(N).
But if I want to insert an element into the middle of a linked list, and I already have a pointer to the place where I want to insert it, that insertion is only O(1). I have to change swap some pointers around (2 or 4, depending on whether it's a singly- or doubly-linked list). But that doesn't depend on the size of the list. Whereas if I want to insert an element into the middle of an array, I have to move all the elements after the inserted item, which is an average of N/2 items, which means that operation is O(N).
This is a completely inadequate explanation of big-O, but I hope it's enough to clear things up at least a bit for you...
[Edit: fixed italics.]
Here is the key insight I was missing. Thank you very much!
Now, if the number of times you had to access the memory in order to retrieve the data in the array depended on how big the array was, then you'd have O(N). An array is specifically designed so you only have to go to memory twice, first to get the memory address stored at X position in the array, then to retrieve the information stored on that position.
A linked list, as described in a sibling comment, actually does have to do this. You trade easy accessibility for other properties.
Ditto for the steps to do register operations and any of the other machine language instructions. The time can vary, but not as a function of the size of the input. So it's still constant time.
To answer your immediate question, the "general computation model" assumes constant memory access time. It's hand-wavy, but at least it's consistent.
The bigger problem is that for hashtables, even under ideal, non-physical assumptions, you still can't logically derive O(1), because there are unavoidable, inherent computations you have to do as the hashtable gets arbitrarily large. Either you a) adapt the hash function to have a bigger output, or b) you allow values to stack up in each output slot. a) is log(n), b) is n.
I don't know anyone who could read the hashtable implementation, without knowing the "right" answer, who would reasonably say "oh, that's O(1), obviously".
[1] https://news.ycombinator.com/item?id=9807739
I wondered about hashtables too. I was actually teaching someone about them recently and had to re-read some CS stuff for it, and in the process I realized that the O(1) access for hashtables doesn't make any sense in the light of explanations I know.
So it turns out that the answer is complicated and in CS curriculum they just handwave you through. It sucks, to be honest, and it's the one thing that always annoyed me about formal education - far too often the teacher/professor stated something as a fact and provided a "proof" with so much confidence that I sort-of assumed it must be so, and realized only months or years later (and after a lot of confusion) that I learned an approximation - maybe a smart one, with good reasons backing it up, but still just an approximation, with important caveats that were never even mentions.
It sorts of make you wonder how much do you really understand about things, even in STEM.
[0] - https://news.ycombinator.com/item?id=9808452
[1] - http://cs.stackexchange.com/questions/1643/how-can-we-assume...
I stated in my first reply that the growth rate is notated as a function of the size of the input. Big O is itself an approximation, you don't use it if you absolutely have to know all the other factors that don't vary on the size of the input. Such as if they vary on your memory architecture. In practice they tend not to matter, Big-O is sufficient for most purposes.
If you do need the detail, you remove the Big-O and write out your other factors so you can compare them to other algorithms at the right level of detail. There are also other notations you can use that convey other concepts, such as little-o, little-theta, big-theta. When you use a Landau symbol[1], as these are called, you're making an approximate statement by definition.
It's still perfectly fine to call array access O(1), even if your data is stored on Pluto, and it's Odysseus doing a space opera Odyssey for each retrieval, you're still only going there twice. Even if there are sub-algorithms that you are calling within the main one, you're still only calling them a constant number of times. If the first time you go to Pluto to get data it takes 6 months and the second time it takes 30 years, because of complications, it's still constant time.
If you were accessing a linked list stored on Pluto, then you're going to Pluto a number of times depending on how deep in the linked list your data is, assuming it's a dumb probe and it can't figure out where to go once it gets to Pluto and has to come back to earth to figure out what to do next. (go back to Pluto)
If it turns out retrieval time matters, or other factors besides the size of the input, then you can't approximate over them and Big-O ceases to be useful.
[1] http://mathworld.wolfram.com/LandauSymbols.html
Given O(1) arithmatic, you should be able to use an O(1) hash function. At that point, you only have to deal with realocation as your tables grows without bound. You can solve that problem by using the 2n allocation method that gives us O(1) amortized appending to vectors.
Of course, you still need to make messy assumptions about randomness.
A hash function with 5 bits of output needs more operations than one with 2 bits of output.
Thanks everyone for chiming in and taking time to write your answers! I did know the general concepts behind O-notation, but no doubt I now understand it even better :).
In the same vein algorithmic complexity can be a fantastic first gentle introduction to theory and it's best when tied into writing algorithms in a data structures class. The same can be said about regexps for example - practical v theoretical aspects - or logic as applied with prolog (or even make) say.
The interesting thing (as seen in a comment below about arrays and constant big-O) is that often intuition goes against the the rigorous understanding - so it's best to have both. I suspect the same holds for language as well. For example etymology of word roots as well as actual writing using the words.
http://english.stackexchange.com/questions/1155/what-is-the-...
Formalizing it would be about as silly as formalizing which music sounds good.
(If that isn't what you mean, then what do you mean? That linguists should carry on, but not look for patterns and rules? Then what, instead?)
Also, what is a "linguistic construct" if we don't have formal rules? Whatever it is, wouldn't it be less ironic to call it a "speaking thingy"?
To say there are formal rules of language is a bit like saying there's only one culture that is fit to judge the acceptability of your words.
Saying the rules shouldn't exist is like saying Newton's laws shouldn't exist -- they are just patterns that someone has noticed.
While there seem to be exceptions to most rules proposed (because natural usage is complex), the rules are still fairly accurate for most cases.
So why do it? To make observations? Observations don't need formalization; just provide good statistics.
Such a poor headline.
What I've learned is that you can't teach any type of rule until all it's "prerequisite phenomena" has been experienced. Music education has a bias of more "doing" and experiencing and less "talking" about (or it should at least). So it has a keen way of turning ideas and concepts into action rather quickly. I think many other disciplines in school can learn a bit from how music is taught frankly: there is a very quick turnaround from concept to application/experience and therefore to emotional context of some sort, which really is the end goal to all learning. Why do you care about X?
So if a rule simply is an equation of some sort, or a statement of relationships, then the prerequisite phenomena is making sure every variable is defined within it; so that one can focus solely on the relationships within the objects instead of the undefined variables. This covers many different grounds depending on the style of the learner and the material at hand. Sometimes (rarely) words are enough (if you're building familiar rules into new rules and the experiential phenomena is all done in the mind "ah-ha!") and usually, a student needs to hear the sound of a major scale vs a minor scale and try to describe it with words before telling them what actually makes it sound different theoretically. And even then, there are different ways to explain it. If the student picked up major scales really well (prerequisite phenomena), I will use the modal approach to learning minor scales (it's the major scale but starting from a different note), if the student picks up the scale tones and is better with spacial relationships, they usually already talk about the differences between what they just played as a sharp/flat 6th or 7th scale tone. And there you have it, they've just instructed YOU how they think about a concept.
Music is a great example of how there is no single correct way to explain the theory. First off, music practice and artistic decisions always came first, the theory came later as people tried to understand and teach it. And it is the bias of educators to find a single correct way to understand it within themselves that leads to them only prescribing one way to do something (memorize this!). Teaching really is listening more than it is speaking.
This is not the case for other cognitive skills, such as reading and (to our point) mathematics. My son cannot learn calculus simply by hanging out in my office. While our end goal may be the sort of effortless intuition in mathematics that we experience in parsing complicated sentences, the process of acquiring those two skills is of necessity widely divergent.
It's just memory, we recite timeworn phrases because that's what we hear over and over.
Non-native speakers use phrases that "sound wrong" only because they are synthesizing from principle or from their own language, and haven't heard the usual phrases over and over.
This is where rule-based language analysis runs aground.
So why, when someone shouts out "Look out for that robot purple tiny Mexican goat!" you would immediately peg them as not a native English speaker, but if they had said "Look out for that tiny purple Mexican robot goat!" you would not?
This is not a 'fixed phrase' thing. There are rules, you're just not consciously aware of them.
I suspect what happens is that students forget some of the good basic ideas (or is that "basic good ideas" ;-) ) they were taught, and teachers fail to re-emphasize them to keep students on track, and so all they remember is the formal/abstract techniques they spent a login time struggling with. Painful experiences stick in our memort more than smooth easy experiences.
[0] - For things you learn to use all the time, or to leverage your cognitive process. The obvious exceptions are things you want to do with mindless precision, where the risk of guessing wrong is unacceptable. Compare public speaking to memorizing a poem, or guesstimating to doing explicit pen and paper arithmetics.
Another science class anecdote - first year electronic engineering, the professor is showing us the derivation of transistor gain formula. He started from pretty much first principles, written out a huge formula, and then started to cross things out - "this in practice is close to 1 so we can ignore it", "in standard operating conditions this is pretty much zero" (and poof, half of the equation gone, multiplied by zero) - and kept going until he arrived at the standard I_c = βI_b. It gave me a new appreciation of just how much engineering is basically handwaving parts of reality away.
Unless we grew up speaking a different language, or were born to people who didn't have English as their first language. My wife has been in the US since the age of 2 and speaks perfectly but she still has a few minor linguistic tics that a second-generation native speaker wouldn't, and is she shy if she comes across a word she's not sure how to pronounce or whose meaning is unclear.
Having taught English as a second language to people from a wide variety of backgrounds, I don't expect anyone to memorize the royal order of adjectives, but it's incredibly useful for them to know that there is an underlying system and to match patterns of adjectives from their reading material against it, or play games with it (like thinking deliberately wrong phrases such as 'old little lady' for comic value), or be able to refer to it if they're nervous about writing something. The same is true for people who miss out on a proper education because of domestic or socioeconomic problems and maybe come to literacy as adults, but never develop the total confidence of someone surrounded by language since birth. Incidentally, those of you who live in California may have noticed the public information campaign encouraging parents to talk and sing to children, especially babies and toddlers. Research indicates that this has a massive influence on brain development and subsequent success or failure in life. See http://www.economist.com/news/science-and-technology/2159692... for an overview.
So yeah, of course the best way to acquire language is to be in a linguistically rich environment, and just soak it up to develop an intuitive understanding that promotes linguistic creativity and wordplay, as opposed to studying it through formal methods and turning it into a philological exercise. But that does not mean that formalism is bad, or that we should conceal the existence of systematic structures from kids in case it will wreck their creativity or something - if for no other reason, than to spare them the waste of reinventing the wheel should they be inclined to adopt a formalist approach on their own initiative. It's very easy to handwave away such rigid-seeming pedagogical tools if you already enjoy the benefits of total fluency, but for those who do not enjoy the same advantages this is the equivalent of pulling up the ladder behind oneself and then critique the confused for poor listening skills.
I don't have a comment on the math part - I agree with the author that we ought to be open to using multiple learning techniques so that each student can find the best one, but I think he seriously underestimates the utility of formality. When I was 5 I thought chanting multiplication tables every day at school was a bit silly, but 40 years later I greatly appreciate the fact that I can handle everyday trivial math problems reflexively rather than needing to reach for a calculator, pencil and paper, or a mental script of how to perform the calculation. Repetitive drills and formal methods are not the best way to explain new concepts, but they are incredibly useful exercises to retain them and make the basic knowledge feel instinctive in later years.
It's been said (citation needed) that phrases like "tick tock" and "see saw" are in those orders because it's a high or hard vowel before the low or soft (e.g. "tock tick" sounds weird). Maybe that is why "little old" lady sounds more correct to us? I don't know. But the article goes off to draw a parallel to mathematical intuition, and leaves the original grammar problem unresolved, in my opinion.
Incidentally, I usually _really_ like the Better Explained articles.
The adjective order rules are interesting in that we have to reverse-engineer them from our brains, but aren't consciously aware of them. It's apparently an area of ongoing research why certain orderings are correct. (Maybe there's something about the specificity of the adjective, where the more-specific items are closest to the subject.)
I think the higher-level concern is we can get tricked by thinking we need to consciously master the structure in order to be fluent, vs. letting our brain's pattern-matching skills do some of the heavy lifting.
I like the view that this is an open problem and an area of active research, much more than the more conventional, lay-person settling of the issue as "developed an ear for the language" and that's the end of it.
The impressive work of people like Steven Pinker and Chomsky (in his actual academic field) is to look very carefully at different ethnographic groups, and the larger cultures those groups are embedded in. By doing so, finding groups isolated enough or with a materially different context, such that they don't exhibit the same patterns.
The title of the article felt like a bait-and-switch, I guess. When I realized it was on betterexplained, it did make more sense that it was ultimately about mathematical reasoning. No worries!
That does make it different from mathematics, where there are reasons for the rules (you can't divide both sides of an equation by a value if that value might be zero, for example). But the point is more to suggest that it could be possible to make progress in carrying out and understanding mathematics without understanding some of the formal underlying rules beneath a concept. That seems like a valid point.
No, it does to a degree. The rules are inferred from observation and internalized, but not precisely. "little" before "old" is a rule, almost motoric. As a foreign speaker I agree that isn't a logical rule :)
edit: I guess, the author is looking for the term heuristic (a general rule that is right often enough, but not precise nor complete).
It's deeply disingenuous to compare effortless biologically-determined learning to effortful general learning and think you can apply lessons from one to the other. Even in the example the OP picked, there's a reason that the learners drill the adjective order table, and it's because without the drill they will never learn it at all. Learning a language as a small child is a different process than learning the same language as a late teen or adult, and the results are very different. (Even so, I wouldn't bother instructing people in adjective order... if they do never learn it, it's no big loss.)
On a different, more technical note, OP doesn't quite understand what's going on in the example either. "Vietnamese spicy food" is perfectly standard English; the ordering there is determined by context. "Vietnamese spicy food" is a subset of spicy food, and will be used whenever it's being contrasted with other spicy food, whereas spicy Vietnamese food is a subset of Vietnamese food, and will be used whenever a contrast is drawn between spicy Vietnamese food and other Vietnamese food. (It's correct, however, that in the zero-context case, "spicy Vietnamese food" is preferred. In my analysis, that's more because people are likely to reify the concept of "Vietnamese food", which makes the phrase structure ("spicy" [adj] "Vietnamese food" [noun]) rather than ("spicy" [adj] "Vietnamese" [adj] "food" [noun]).)
http://mysite.science.uottawa.ca/mnewman/LockhartsLament.pdf
So everyone has a different spidey sense.