OOP Isn't a Fundamental Particle of Computing

The fact that OOP was really bolted onto Python as an afterthought means you can learn simple straightline code, then start clustering it into functions as it starts to get more complex then, eventually, start clustering functions and data into simple classes where it (occasionally) helps to manage the growing complexity, followed by your own modules. You don't have to start with packages and class hierarchies just to print "hello, world" as in Java, but you also don't have to reinvent the string, as in C.

My big issue with OOP is that it injects unnecessary complexity when used as a catch-all. Alan Kay advocated OOP as something to do when complexity became unmanageable: encapsulate it behind simpler interfaces. That's a good idea! Unfortunately, the OOP fad dovetailed with the 1990s-ongoing attempt to commoditize programming talent and we ended up with a generation of mediocre programmers who took OOP to mean "Go out and build massive, complex, over-featured objects", not "Here are tools to reduce complexity when needed". Alan Kay's original message was hijacked, producing the monstrosity of corporate OOP.

When I advocate FP, I usually put it like this. Instead of having 23 poorly-understood and often badly implemented design patterns, functional programming has two design patterns: Noun and Verb. Nouns are immutable data: from integers to record types to OCaml's unions to Scala's tree-based Map and Set. (Occasionally Nouns have to be mutable, which means they have attached Verbs. I'm glossing over that for now.) Verbs are functions-- when possible, referentially transparent. We can also use the latter as nouns, which gives us cool "combinators" like map, reduce, and flatMap/mapcat that help us to compose functions.

There are two annoyances we hit with "programming in the large" when we're restricted to nouns and verbs. One is namespace collision, and the object-oriented solution (see: Scala) is to have locally interpreted functions, or methods. That has advantages and disadvantages, but is sometimes the right solution. A related issue is the Adjective Problem-- how to handle similarities, such as objects with a "close" method or collections with "foreach"-- which Haskell solves with type classes, Ocaml with functors, and Java with inheritance. The issue I have there is that it's hard to solve the Adjective problem using "modern" OOP without injecting non-locality into code comprehension, and we learned a lesson about extreme non-locality with Goto. I am not the world's biggest fan of inheritance.

The core idea of object-oriented programming-- that you should hide complexity behind simple interfaces and expect the application programmer only to know the latter-- is solid gold. That's why you don't have to learn a whole new language whenever you move to a different SQL database (or a later version of the same one): the implementation changed, the interface (or, at least, most of the parts you care about) didn't. The problem is that it's really hard to get interfaces right, and average corporate programmers don't have the ability.

Professional programming, by the way, is all backward. The way to become a decent programmer for realz is to start on very simple, self-contained projects like scripts for data analysis, and move upward to more complex programs once you get the non-trivial architectural problems associated with simple ones down. The Unix philosophy (small components, large software solutions being respected as systems rather than thrown together as one giant single program) is superior in general, but especially when people are learning how to write software. You don't learn software architecture except by doing it, and starting small gives you the quick feedback cycle that helps you learn. Corporate programmers in OOP-land often never get the architectural experience of writing systems (starting with small ones) from scratch. Instead, they spend their 40 hours maintaining and tweaking large monoliths other people wrote, and this is a big part of why they never improve.

But how about substring search? Using Python's string.find instead of something like a suffix tree certainly carries more than a constant time penalty (Obviously for memory complexity it's the other way around in this case). The same goes for blindly using a standard Python list when you plan to insert lots of items in the middle.

Not knowing the complexity of operations on standard data structures inevitably leads to "basic algorithm mistakes". How would you choose a good algorithm without knowing the datastrucure it's operating on?

I think what you and DanielBMarkham are approaching from opposite sides is that it's useful for a student to learn both how computers work and how computation works.

C is pretty close to the computer. Learning C will teach a student how computers work. That's important for the same reason that a fashion designer should have some understanding of what shoes are made out of and how they're assembled. Making shoes that are nice to look at, but that fall apart when worn is not especially useful.

Python (or Smalltalk, or Scheme, etc...) is closer to how computation works, and closer to how many of the problems people want to solve using computers work. It lets students explore what they can do with computers without getting mired down in the details of how the computer will accomplish the task.

Java is somewhere between, and from an educational perspective, has the disadvantages of both sides without gaining many of the advantages.