Hacker News new | past | comments | ask | show | jobs | submit login
Big O Notation – Using not-boring math to measure code’s efficiency (interviewcake.com)
178 points by rspivak 79 days ago | hide | past | web | favorite | 95 comments



I've noticed there are SO many of these "coding interview prep" courses lately. Like, obviously it's a hot job market, but there's just so many and of a certain vibe that it seems like some are selling a dream.

There's a common narrative too, that it's all about algorithm question prep and it's a "game" you can win. One youtuber who recently landed a ~$275K TC gig said it's not about being "intelligent" it's about practice and rapid pattern recognition (he also was pitching his own coding interview prep course). Said he forgot half of it after getting the job.

This could all be true but this narrative is coming from sources that have a financial interest in making you believe that. What do you think HN? I mean I know algorithm prep is an important part of the interview but.. there's just something sketch about all these outfits I can't quite put my finger on.

(I also wonder if the people who get hired based on prep vs. aptitude then have a kind of survivor bias and hire others who are strong on this limited range of pattern recognition... could it be a problem for the industry?)


It depends on the company, but most of the FAANG company (and others that try to imitate them) interviews come down to how quickly you can get the optimal solution on the board. It has very little to do with how well you can code day to day.

Most interviews have 4 sessions broken up in the following manner:

1 hour: coding

1 hour: coding

1 hour: lunch

1 hour: system design

1 hour: cross-functional

In my experience though, the first two are the ones that really make or break candidates, if you don't pass both, you're not getting hired. And yes, most of those interviews just test your knowledge of how quickly you can figure out the right data structure and algo for the question at hand. And even if you know all of the data structures and the applications of each, it can be incredibly difficult to solve the problems in the allotted time.

The other funny thing is that your previous experience doesn't do anything for you other than maybe getting to skip the technical phone screen. Everyone goes through the same process. e.g. https://twitter.com/mxcl/status/608682016205344768?lang=en

On the bright side, it does look like many companies are now realizing this isn't a great way to evaluate someone's ability and are beginning to incorporate more practical exercises.


> The other funny thing is that your previous experience doesn't do anything for you other than maybe getting to skip the technical phone screen. Everyone goes through the same process

You could also argue that this is fair chance between those who just came to the field.

> On the bright side, it does look like many companies are now realizing this isn't a great way to evaluate someone's ability and are beginning to incorporate more practical exercises.

It's the other way around: many more companies are incorporating Leetcode style interviews as their first "filters" either via online test or quick on-site.

Here's what happened: it used to be the case that only these FAANG companies have the resources and the know-how to either create these "trick" questions or picked a few from their favourite Algorithms book "exercise" part.

These days thanks to many "algo" challenge websites (like InterviewCake.com) that not only provides questions but also correct, detailed, and optimized answers, it is getting easier for employers to just pick a random ones and use that as interview materials.


This is the first time I've heard this characterization of Interview Cake as making the Google-style whiteboard coding interview accessible to small(er) companies.

It /might/ be /somewhat/ true. But I'm skeptical.

Anecdotally, when I started Interview Cake 6 years ago it was already true that most small companies my friends and I interviewed with were using these sorts of data structures and algorithms questions. The handful of exceptions were mostly companies that were outside the "scene" (usually because they weren't in SF or NY).


I live in a hi-tech city outside SF/NYC and I can confirm that many companies in my area filter candidates using questions straight from leetcode.

This was not the case 5-6 years ago.


Where I work we give people real problems to solve during interviews. We have a great team that gets a lot of work done. In hiring we put emphasis on practical expertise with the tech we use and the problems we face and not academic puzzles. There's immense value in having a strong computer science background and I feel we've had success being able to get a sense in our candidates where they stand without the standard whiteboard hell other companies put their candidates through.


Can you give an example problem?

I wonder how rigorous non-algo challenges can be inside of an hour. Or how you would “get a sense” of CS fundamentals without algo tests.


I can do one quickly. I need to take affiliations from papers and work out which organisation(s) they're talking about. How would you solve this problem, assuming the affiliations are already extracted for you?

What are the top level concerns, how do you break that problem down, how might your problems scale, etc. There's a lot of questions I'd expect to get to, and this should be something done along with the team kind of like we're all working on the problem together.

I find it useful to see how well people can talk through the problem, it can lead easily into questions about licensing and rights of reuse, types of errors, etc. If they suggest an approach they've used before, can they explain likely failure cases / benefits? Are there workarounds, detection methods? For example, if you're doing text classification then tfidf+svm is a solid first thing to try, and there's easy ways that can fail which we could talk about.

There's a lot of that you can cover in an hour, and it tests whether someone can explain a potential solution to the team effectively, just as they would have to on a day-to-day basis. We can bring up specific types of problems that we face within it, what we've tried, and we can constrain the problem more or lead someone to starting points if it's a bit overwhelming.

edit - I guess this would fall under some data science fundamentals, but the approach I think works for CS fundamentals. What data structures could you use? What are the tradeoffs? It's not about finding the one optimal solution, but about how to proceed.


> For example, if you're doing text classification then tfidf+svm is a solid first thing to try

This is screening for specific domain knowledge (text processing) not general programming aptitude. That's ok if you want specific kinds of prior knowledge on Day 1 but it is not a way to hire generally smart people.

> I guess this would fall under some data science fundamentals, but the approach I think works for CS fundamentals. What data structures could you use? What are the tradeoffs? It's not about finding the one optimal solution, but about how to proceed.

This is exactly how most algorithm interview questions work.

I'm trying to understand what the OP meant by "real problems" not "academic puzzles". It sounded like they avoided hard algorithms yet "got a sense" of CS fundamentals somehow.


> This is screening for specific domain knowledge (text processing) not general programming aptitude. That's ok if you want specific kinds of prior knowledge on Day 1 but it is not a way to hire generally smart people.

Not really, the domain knowledge here is much more the bibliometrics stuff, which we don't need usually. What I do need is someone who knows that they can't just take any data source they find and throw the latest deep learning hotness at it and call it a day because the F score is over some random threshold.

You can absolutely use this to hire generally smart people, what you are right about is I won't be hiring people who are generally smart but have no basic understanding of any of the types of solutions they'll need to work on and with. Based on team size and where we are, that's completely fine for me right now.

I think this helps find people that:

1. Are able to talk through a problem

2. Understand the kinds of issues they may face, and discuss how to go with that (including business level work, when to / not to use humans, etc)

3. Have experience working on the kinds of problems they are going to face

The tfidf+svm example was not intended as "ah yes, they said the algorithm I wanted" but as a springboard into a further discussion. Maybe they talk about word vectors, whatever, can they explain what the pros and cons are? Where might it fail, or more importantly what would they want to test? Where do we get training data, how long might that take for reasonable quality, how do you measure that, etc.

> This is exactly how most algorithm interview questions work.

The puzzles I think they're talking about are "here is a theoretical problem, find the optimal solution". Like "you have X eggs and need to find the highest floor you can drop them from without them breaking" or the classic "implement a doubly linked list with a single pointer" despite the fact _almost nobody_ would actually implement that.

I'm talking about giving an actual issue they're likely to face and talking through it. Maybe that's "how would you implement user flow for X, given that we've got institutional customers with multiple clients" or "we need to do rate limiting and have X servers, how would you go about that?". For the latter that might go into a discussion on what the problems are with different approaches in complexity, what the cost is of letting someone exceed their rate, of cutting someone off early, etc. Those aren't really my field so maybe the questions are a bit off, but the point is can they contribute to a discussion on the way forwards on a problem which represents something they will realistically face.


I wish people would stop quoting that tweet. mxcl doesn't know how to work at a big company. He failed miserably at Apple as a result, and he would have done equally as badly at Google. The success of Homebrew has more to do with product fit than actual technical ability.


I wish the usage of FAANG would die. Firstly it exlcudes obvious others like Uber, Microsoft, etc. Secondly, and purely aesthetically, it sounds silly. I hereby propose we call such companies the Big N, and I'm definitely open to other ideas.


Do Uber and Microsoft pay as much as Facebook/Apple/Google/Netflix/Amazon? The acronym exists for a reason. I think Amazon only makes the list because of how well their stock performs, but it still deserves to be on there because of that.

The only large company I can think of that matches or even exceeds the offers those companies give out is (surprisingly) Snap. If we go smaller, Airbnb and Pinterest are up there too, but they don't have nearly as many employees or open positions.


It's wildly misused if the reason that it exists is pay. Even the parent to my comment is talking about interview process; I doubt that varies much from any of the "FANG" companies vs. Microsoft, Uber, etc.


I’m not a fan of the acronym either, but it’s what people know, so I use it. Big N is much better, I’m onboard.


Why Netflix?

Gmafia


More generally, why do we have such a fetish for acronyms in general? Is it some kind of insider feeling to know a "code" for a thing?


Pattern recognition and aversion to repetitive behaviour on a micro level. Ironically oblivious to the repetition on a macro level that is most of our entire lives, but that’s another story :)


An insider feeling is a strong likelihood


Brevity.


> most of those interviews just test your knowledge of how quickly you can figure out the right data structure and algo for the question at hand

Not sure that's true. Just a few days ago someone was commenting here how they were a frontend developer with a few years of experience, yet they didn't know what a for loop was. These interviews aren't about how quickly you can figure out the right data structure, they're about separating developers from "developers".


A simple fizz buzz will solve for that. No need to put in algorithm questions.


FizzBuzz establishes a minimum baseline, but you need more than the ability to write FizzBuzz to be able to work at a FAANG.


Do you really need to be able to "invert a binary tree" to move a button in gmail to an even less convenient location? It's not even that you need to know all those things to work at many positions in FANGs. It's about making sure that someone who can do that does not, God forbid, go somewhere else and does something actually useful for the humanity.


I've never been asked to "invert a binary tree" while interviewing at Google, or anything of the sort; later, as an interviewer myself, these kind of questions were forbidden. Everyone knows they're stupid, and they've been forbidden for a long time. I'm starting to believe this is either a persistent myth, or something the other companies, but not Google, does.

In my experience, all the questions I was asked were fair game - all of them were about implementing a toy version of a real-life feature (simplified for the time constraints of the interview). All of them felt like "yeah, a competent engineer should be able to do this".


If anything, a myth that persistent must have something behind it. (I've zero interest in FAANGs so I would not know if they do or do not really ask it).

There's no question that a competent, well-rounded programmer should know about these algorithms' existence and when to use them. But whether testing if said programmer can implement them from scratch during an interview... that's a million dollar question whether these questions provide optimal outcomes. Anecdotally, yeah, sure, I did these things. In S/370 assembler at that. But did I use 90% of them since then(and that was when Apple was the only FAANG in existence)? No. So I think the feeling is that this kind of interview tests not so much how good, or experienced, or what not, you are at programming but rather how desperate you are to work at that kind of company to spend a good amount of time memorizing algos and data structures you've learned and forgotten years ago.


Sure, but there's a huge difficulty range between Fizzbuzz and that "come up with a dynamic programming algorithm on the spot" crap that Google and friends like to do. (And that range includes problems that are actually relevant rather than algorithms class homework.)


Yep, agreed. Fair enough.


A major force driving this is the employers who choose to conduct interviews in this way.

I'm a developer with about 6 years experience in full stack web app development (Rails & Django mostly), and I recently got my ass absolutely kicked during a couple of live coding challenges that were very heavy on theory (also worth mentioning that I'm a self-taught dev without a CS degree).

I started talking to some former coworkers about my experience, and I got 2 main responses: A) it's imperative to have a CS foundation regardless of your degree if you want to advance in your career, and B) employers only consider prior experience to certain degree.

The two interviews that I bombed involved heavily contrived coding challenges that tested CS fundamentals in ways that I've never encountered in a professional environment, so it doesn't surprise me at all to see services like this popping up.


I don't have a CS degree either, and I have yet to pass so much as a FAANG phonescreen (I'm 0 for 3), but I'm both glad and grateful that the employers that pay the most also care the least about your education or past experience when it comes to the interview process.

Compare it to equivalent high-paying fields like finance or law, where you can hit a career ceiling based simply on what school you went to.

I hate studying for tech interviews. It feels like a sisyphean task, since I'll get really into prepping for a few days, then taper off until I've forgotten everything. At least it's easier to start up again the next time. This is now my third time attempting to prep.

I wish I was brave enough to just quit my job and spend 2 months studying. I'm in SF now, and all of my friends here make at least $300k when counting stocks and bonuses. I'm just barely short of half that (with no stocks or bonuses), and getting there is my next big career goal.


To be clear I think it’s good to test CS fundamentals even if you don’t use them every day. It’s a good screen for aptitude. I’m just concerned that taken to the extreme it mistakes excessive pattern recognition prep for true comprehension and aptitude. Especially if it’s “whoever puts the optimal solution on the board fastest wins.”

I do think it would do you some good to read up on core CS and algorithms though. I also did not get a CS degree and learned in the field, but now having studied up on it I feel much more in command of my craft. They do come into play now and then, it’s not just brain teasers. It does take weeks to months to really learn it though so I understand the resistance.


A strong CS foundation is hugely valuable and I don't think anyone will argue that but the fact that someone with over a decade of experience can go from a "no hire" to "hire" after a couple months of practice tells me that we aren't testing for the right skills.


Being exactly of those people (experienced but would have failed algo screen and had to brush up), I can confirm it would have false negatived me despite years of competent productivity... and yet I also feel I have filled in some significant gaps that I was lucky to avoid previously.

I think if you have a really strong “portfolio” of individual work that can be validated as being yours, like side projects, that can be a valid pathway into at least non senior roles. Maybe you’re weak on algos and other team members can help out at key points.

But I don’t know a better objective and direct measure of coding aptitude inside of 60 minutes. My issue is not with it in principle, at least for senior roles. It’s taking it to an extreme and misinterpreting the results. It gives this false sense of certainty about aptitude.


> I’m just concerned that taken to the extreme it mistakes excessive pattern recognition prep for true comprehension and aptitude. Especially if it’s “whoever puts the optimal solution on the board fastest wins.”

I agree with you on this. They do have taken this to the extreme because the questions are getting harder and harder.

This is hard tbh because if you're an employer whom used to be able to filter candidates by asking "easy" algorithms questions and woke up one day to only find out that everybody knows the answer, what will you do?

"It used to work so we just have to improve it, right?" => make a more challenging questions.


Improvement doesn't mean making it harder. SAT questions don't get harder every year (ideally). They're just different. It takes effort to come up with something different and novel though. Most places don't.

Maybe that's what the industry needs.. its own SAT. Heck man, that would make interviewing a lot better. You take one brutal test over a few hours, get your score, and then apply to multiple companies. You don't have to do dozens of whiteboard code interviews. Job postings specify score ranges. There's different score components (algos vs system design, like math vs verbal).

I guess there are startups like triplebyte trying to do that, but they're not as independent as the SAT. They make money off hires.


I would argue that we are going toward that direction with slightly different variation/format.

Faang and multiple SV companies will ask 3-5 LeetCodes with 1-2 System Design. Some started to incorporate behavior question (like Amazon with 14 LPs)


>what will you do?

You'll do the same thing most other professional industries do. List the requirements for the job: x to y years experience with technologies a,b and c. Grab a handful of the most polished resumes, interview them for personality, and hire the one you liked best.


Previous method works well,why change it?

Silicon Valley thrive in tricky algo questions. That's how they hired engineers since long time ago.


But CS is not only about algorithms and data structures. Even schools are missing the point mostly. Things like general PLT and formal methods, namely how to deal with abstractions in a large project, and how to know if your program is correct, are mostly ignored because they're not favored by the market.


Self-taught as well. It’s a game. All the big name software co’s and the startups founded by former big name software devs like to play it. Heck, I’m starting to enjoy the game (primarily because I have exceptional pattern recognition skills).

I was failing interviews too until I picked up an undergrad CS algorithms book and read through the first few chapters on data structures and theory. Then I signed up for LeetCode premium. After a couple months of reading and practicing, I was getting an offer from every place I interviewed at. Now I’m at one of those big name software companies, and if I’m ever asked to interview a candidate—well, I don’t know what I’ll do. Maybe something with a binary search tree. I’ve literally never had to use that in 8 years of development. :)


Do you think any of it made you a better programmer or architect?


Maybe you should start a coding interview prep course...


As a DevOps guy who's been screened out of companies that care about such things, I'm a mix of horrified and skeptical.

I'm horrified because I'm seeing some gross incompetence in the realm of organization in thinking, clean infrastructure and security awareness. And some of this punishes the old(er).

I'm skeptical because I think many of these interviewers are themselves lousy systems people, are building environments that may need to be bailed out one day, and to boot are probably not people persons. A people person can sense better how to conduct an interview to feel out how to determine whether the candidate is clever and useful.

I took a managerial route so I'm mostly immune now, but boy do those cocky coding interviews stick in my craw when I think about them.


Having the same experience and background as you I took a different perspective: I use that system of interview to filter the companies _I_ don't want to work for.


I work at Google. I think it's half true.

I would not have passed the Google interview if I had not prepared. After 3 years, I have completely forgotten most of the prep. I couldn't even implement a binary search right now.

That said, I do have an innate ability for problem solving. I know another person, who has prepared significantly more than me (multiple months full-time) but still wasn't able to get an on-site interview. In my opinion, it requires at least a minimum level of intelligence, luck and preparation.


I get the sentiment but come on. I seriously doubt you cannot even implement a binary search right now.


It's true. Obviously I could do it if I could look it up or if I could look it up, but not on command.


> I've noticed there are SO many of these "coding interview prep" courses lately. Like, obviously it's a hot job market, but there's just so many and of a certain vibe that it seems like some are selling a dream.

It's akin to the Fitness world. There are tons of people selling proteins whey, their fitness apps, fitness set "reps", etc. Can't blame them, they're selling what people want.


What’s wrong with either of those?


I have found pair-programming with a dev on a current problem you have in your codebase to be the best litmus test.

If u want to give "quiz" interviews, u will get employee's good doing them. Like those CS grads in my class who copied eachothers take-home assignments yet still passed because they were good at memoizing.

Furthermore, this is the first training session for your future employee - you are inducting them into your companies culture. If "answering meaningless questions for the sake of it, is what you want to portray to them. So be it." They have been warned!

Selecting for a certain subset of people, is a business decision. Be aware of what interview practices mean in the context of how that company operates. If the job add has a sticker list of tech-hype, a promise of re-dev'ing a monolith into k8 microservices, with a leetcode interview, you already know alot about that company!


> I have found pair-programming with a dev on a current problem you have in your codebase to be the best litmus test.

This has its drawbacks too. You're biasing towards familiarity with your code base's specific tech stack. Good engineers can learn new tech stacks in days/weeks, so that's not that important to screen for.

Plus "everyday" code is a lot of plumbing and busywork, so it's not as good a screen for intelligence. Algos at least cut to the "hard stuff".

> Like those CS grads in my class who... passed because they were good at memoizing.

Getting good at memoizing would be a perfectly fine reason to pass a dynamic programming class. :-)


I love your insight, but I don't know much about these courses. Even though I am myself prepping for an interview, I'm just reading CtCi and building the structures and algorithms myself.


I'm pretty sure that Interview Cake is at least five years old at this point.


> not-boring math

What's next? Gradient decent with no gradients? Fourrier transform with no functions?

If math is do boring just skip the whole thing, don't try to kid yourself by saying you're not doing it when you are in fact doing it.

/rant


I was really hoping that this was going to be some lively new way of thinking about or teaching big O notation, "Eulerian path runtime grows like the velocity of a car that drove off a cliff but Hamiltonian path runtime grows like the number of plague bacteria in a petry dish."

I was disappointed.


What's with this gatekeeping attitude?

Big-O notation is a useful tool in a programmer's belt, knowing the math behind it in details is less useful. What's the problem? It's the same thing as not needing to know how an engine works to be able to use a car


That analogy does not really work. To use a modern car for transport, its power source can usually be treated as a black box, but if you don't know the math of Big-O, you don't understand it, and if you don't understand it, you may be unable to apply it in a situation where you have not rote-learned the answer, or, worse, misapply it without noticing. I have seen enough of this to know that it is a real problem.


That is not my point.

Big-O notation is a mathematical notation. By using it, you are using math. It's the same as using a car and saying you are not using a car.


The post isn‘t saying that Big-O isn't math, it is saying Big-O is "not-boring"(->interesting/exciting/whatever) math.


This article misses an actual definition of Big O.

This forces us to skip crucial points like why O(n^2) truly identically equals O(n^2/2 + 5n). The author instead seems to think they are approximately the same because the lower order terms are small compared to the highest one.

We only need to explain the definition and the reader could understand why an O(n) algorithm is in O(n^2), why some O(n^3) algorithms are much faster than others in O(n^~2.4), etc.


> The author instead seems to think they are approximately the same because the lower order terms are small compared to the highest one.

In fairness, this is actually why we care in practice about asymptotic issues. The fact that there is a rigorous mathematical viewpoint that makes them strictly comparable is helpful for being confident about the non-trivial results -- but the reason we care about it is because we want to know roughly how expensive our code is (or will be).


> As n gets really big, adding 100 or dividing by 2 has a decreasingly significant effect.

I was annoyed to see that comment about division, as of course dividing n by 2 has exactly the same effect regardless of the size of n. This is not the reason we ignore multiplicative constants in complexity analysis.

It reminded me of the joke that Earth's circumference is pretty much the same as its diameter, since the the size of pi is negligible at that scale.


> This is not the reason we ignore multiplicative constants in complexity analysis.

What is the reason?


One part is that Big-O is an upper bound that kicks in for sufficiently large n.

For example, a O(log(n)) function will be faster than a O(k * n) function, for any fixed k, when n>j (for some fixed j i.e. when n is large enough). When comparing major classes of functions (n, log(n), 2^n, etc,), constant multiples don't matter, mathematically.

The other reason is that when comparing two functions with a similar amount of constant steps, let's say 5n vs 2n, it's impossible to say which is faster in the real world, so it's simpler and just as useful to collapse the set of O(k * f(n)) functions into O(f(n)).


One possible answer is that any algorithm can be sped up linearly: https://en.m.wikipedia.org/wiki/Linear_speedup_theorem . (At least theoretically, for runtimes bigger than linear.)

Another answer could be Moore's law: machines do get faster over time. (And also memory gets cheaper.) And so we wish to define efficiency (time or space) in a way which does not depend on the current technological state.


That theorem just indicates that Turing Machines with an unbounded/arbitrary number of symbols is a poor model; the approach there will not work on any actual machine. If you take out a factor of 2 in an algorithm, that's going to asymptotically double the state regardless of what actual machine you're on, so I don't buy machine-independence as a reasonable excuse. The actual reason constants are ignored is because it makes the math a lot simpler when you ignore them.


Except Big O Notation is exactly not measuring code's efficiency.


That depends on your definition of efficiency.


You're an engineer, aren't you? Just do the damn "boring" math.


> Big O notation is [...] about how long an algorithm takes to run.

My former prof would have me spanked for an imprecise statement like this.


Original author here. Thanks for the post! Would stick around to answer questions but I'm on vacation in Japan right now!

We're doing a poor job with navigation on the site ATM, so here are some "you might also like" hits for you:

A piece where we derive most of the main data structures step by step, starting with naked bits in RAM: - https://www.interviewcake.com/data-structures-and-algorithms...

A reference / cheat sheet for the main data structures: - https://www.interviewcake.com/data-structures-reference

A reference / cheat sheet for sorting algorithms: - https://www.interviewcake.com/sorting-algorithm-cheat-sheet


It's true that most engineers are not going to implement a binary search algorithm or an optimizing compiler during the course of their employment in a typical year.

However, CS fundamentals are the language of software engineering. It's important for engineers to be able to communicate efficiently about things like runtime analysis, indexes, concurrency models, type systems, etc.

Your mechanic knows how a carburetor works, (s)he knows how brakes work. Mechanics have a common set of fundamentals that they all know and share, and can use to communicate with each other about their work. The purpose of this knowledge is not to be able to fabricate new car parts, although given time and the right equipment, it could probably be done.

The purpose of CS fundamentals is not to so much to implement complex algorithms, as to understand how to use tools and libraries that are based on them.


Question: At what point in a career do you expect someone to have gone from "I know Big O" to "I know how this data structure is laid out in memory on this OS?"

My experience says really good engineers know the latter, but I'd like to hear if this holds for others.


How data structures are laid out in memory has nothing to do with the operating system


OS typically dictates ABI, ABI dictates memory layout of structures, among other things.


    def print_first_item(items):
        print items[0]

    This function runs in O(1) time (or "constant time") relative to its input. 
If this were C where the only types are fixed-size, that might be true. But in Python it seems like items[0] could display as 10 gigabytes of JSON.

And if stdout is piped to a process that isn't consuming its input, it might never terminate naturally.

Also, since Python has arbitrarily large integers, an expression like "index += 1" probably runs in O(log(index)) time, not O(1) time.


in C, it items[0] could segfault, the fault could be caught by a signal handler which does some unbounded amount of work, then populates the appropriate memory location and returns...

More realistically, the page of memory that items[0] is sitting on could be swapped to disk, requiring the OS to do some big operation.

trying to write a piece of code with the big-O you are looking for generally has a huge number of caveats. I'm undecided on whether this is a feature (abstraction) or a flaw (easily misleading)


And "print items[0]" is actually O(n) where n is the size of the string. Maybe even O(n^2) if the item is a big number and a binary to decimal conversion is required.

But it is doesn't matter here because we have chosen n to be the size of the array, because it is what we are studying.

Here it is big-O "constant time" because the execution time doesn't depend on on the size of the array, assuming it is really big. Not that every call of the function will take the same time to run.

The reality is much more complicated, with things like caches to take into account. As a result, complexities under O(n) often don't mean much in practice. But the higher you go, the more important it becomes. As you get to O(n^2) it is time to take a hard look at your algorithms, or make really sure that n is small and stays small.


I think you (and others) are misunderstanding the purpose of the big-O notation. It is used to discuss about algorithms, not about their implementation.


Similarly, if you were to write a O(n) Python program displaying the Fibbonacci sequence, it would not run in O(n) time but it would still take O(n) operations. It only makes sense to treat time complexity literally, if operations take fixed amount of time (int addition in Python doesn't).


Int addition never takes constant time unless your ints are bounded by a constant. Which is why serious people use bit complexity, or otherwise take into account the word size of their machines. Very serious people also take into account the number of memory accesses and the amount of memory used, as you can't address arbitrarily large amounts of memory in constant time either.


Am I the only one who signed up for interviewcake on a whim (similar to those January fitness club resolutions)?

Then I sort of had an epiphany. When will I need this? (or rather "I am too old for this...") I must be the perfect customer for interview cake: paid but do not use it.

I make my own work and those kind of problems just do not come up.

I mean CLRS was fun a long time ago, but it seems to degenerate into skeet shooting pretty quickly:

“Shooting skeet eight hours a month was excellent training for them. It trained them to shoot skeet.”


I have a question for those with a better understanding of such things. Is it difficult to calculate time or memory complexity of a function through static analysis?

It seems kind of basic, but I still find myself manually checking code instead of relying on a tool.


For a completely arbitrary program, it is not possible to calculate a tight bound on the time or memory complexity of that that program via static analysis. See Rice's Theorem[0].

It is possible to determine interesting properties of programs if you weaken your requirements to approximations and/or add significant constraints. You can maintain properties by construction if you only allow yourself to use certain kinds of building blocks in assembling programs. The less powerful your computational model, the easier it is to prove things about it.

The core idea of a type system is to form a symbolic representation of the semantics of your program which is simpler than the program itself, so that you can prove properties of that simpler system instead of the intractable problem of doing so for the actual program. (If you aren't careful, your type system could end up sufficiently powerful that it is itself undecidable, and you're back where you started.)

[0] https://en.wikipedia.org/wiki/Rice's_theorem


> For a completely arbitrary program, it is not possible to calculate a tight bound on the time or memory complexity of that that program via static analysis. See Rice's Theorem[0].

That theorem proves that no general algorithm exists. That doesn’t mean it can’t be done for a particular program. The real challenge is that modern compilers and processors will execute in a way that is hard to predict from source code.


The question was whether it is hard to determine the space/time complexity of ‘a’ function, which firmly placed the question in Rice’s theorem grounds.


If you need precision good enough for practical applications, it’s very hard to do. All modern CPUs are pipelined, time they spent on every instruction depends on neighbor instructions + data dependencies between them. All modern CPUs have multi-level caches, static analyzers must also simulate what data is in which levels of caches; for many practical problems RAM access dominates computations and L1 cache is ~2 orders of magnitude faster than main RAM. All modern CPUs have very sophisticated power management, they scale frequency based on temperature, they selectively turn on/off their blocks, this too affects time. All modern CPUs have multiple cores, L3 cache is often shared across them, all caches suffer heavy penalty when a line is shared across cores. And so on.

People don’t do it not only because it’s hard, also because running the function and measuring time + memory is much easier, also much more precise.

Even if you don’t care about time and memory complexity and only care about these useless O(N), it’s still very hard because complexity depends on input data. E.g. bubble sort is O(N^2) but it can also be O(N) if the data is mostly sorted already and only a single element needs to be moved.


The resolution of the Halting Problem shows you can't even determine whether the complexity is finite!


Yes and no - if the function operates on a balanced tree, you might need some way of encoding the constraints the tree follows, and even just describing what “n” is. But if you’re doing merge sort, the function may take n as an integer, and recurse with n/2 and n-n/2, and that is tractable. But generally, no.


Yes it's difficult, but people try anyway. The term to Google for is WCET analysis:

https://en.wikipedia.org/wiki/Worst-case_execution_time#Auto...


I would argue it isn't tractable.

f(n) = f(n-1) + f(n-1) has runtime O(2^n); f(n) = f(n-1) + f(n-2) has runtmie O(~1.62^n); f(n) = f(n/2) + f(n/2) has O(n log n); for i = 1 to f(n) has runtime f(n).. good luck determining a function output through static analysis


In both cases it has O(2^n). Normally speaking, this response would be pure pedantry [0], but for static analysis it might be good enough. In most cases, the naive answer will be good enough, and the tool can direct you to pay attention to areas of particular concern.

Getting static guarantees about performance would require carefully constructing your code with the tool in mind.

[0] Although I still find it outrageous that CS departments describe their algorithms class as "math" when they do not accept this answer.


They’re asking for the tightest upper bound.


There's master theorem though...


Given a sufficiently restricted syntax, any static analysis is possible. So the question isn't especially useful with the current wording.




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: