This is legitimately a good post.
WTF Is Big O Notation?
41–50 of 101 posts
Re: WTF Is Big O Notation?
#42Earlier quoted context omitted.
No, that algorithm is O(1). 50 is a constant. As n -> infinity, the algorithm runs in constant time. Specifically, I can pick some number C such that C * f(n) > the number of operations, then the algorithm is O(f(n)). So I choose f(n) == 1, and C == 100. Then the runtime of the algorithm is 1,1,1,1,1...., 50,1,1,1,1,.... For all values of n, this is less than C * f(n) == 100, a constant, so it is O(f(n)). f(n) is 1,…
Yes you're right - let me modify my contrived example and say 'at exactly midnight, the complexity is O(n)'. (the cool part about contrived examples is that you can keep making things up until it fits - now I'm just hoping I didn't miss something again like the first time :) )
Still doesn't work. Waiting one minute is constant time. (to be clear, I'm going to be able to come up with a counterexample for anything you throw at me because you're assumption here is just false, in general an algorithm that is O(f) for all values except n is O(f), because you can pick a constant greater than n, no matter what the dimension n acts in is).
(If you reject that and claim that just because I can construct an algorithm that is O(1) from yours doesn't mean that your algorithm is O(1), I'll point out what you presented isn't technically a function, since its not mathematically pure, so the concept of Big-O is ill-formed)
Re: WTF Is Big O Notation?
#43This seems like a good time to bring up one of my pet peeves about big O notation. Every theoretical model I've ever seen says that indexing into n bits of memory takes O(1) time. That's obviously impossible: - The pointer you need to read is log(n) bits. - The physical memory is at best O(n^(1/3)) distance away from the CPU, and thus takes that much time to get back to you. In reality it's probably O(n^(1/2)) becaus…
There's a nice series of articles on this here: http://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html
Re: WTF Is Big O Notation?
#44This seems like a good time to bring up one of my pet peeves about big O notation. Every theoretical model I've ever seen says that indexing into n bits of memory takes O(1) time. That's obviously impossible: - The pointer you need to read is log(n) bits. - The physical memory is at best O(n^(1/3)) distance away from the CPU, and thus takes that much time to get back to you. In reality it's probably O(n^(1/2)) becaus…
There's a nice series of articles on this here: http://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html
Oh cool, hadn't seen that!
Re: WTF Is Big O Notation?
#45This seems like a good time to bring up one of my pet peeves about big O notation. Every theoretical model I've ever seen says that indexing into n bits of memory takes O(1) time. That's obviously impossible: - The pointer you need to read is log(n) bits. - The physical memory is at best O(n^(1/3)) distance away from the CPU, and thus takes that much time to get back to you. In reality it's probably O(n^(1/2)) becaus…
There was a decent article exploring the timing between memory accesses, and when they started taking longer b/c you hit L2 cache, L3 cache, main RAM, swap, etc., and eventually showed how if you really graphed the access times, the overarching "curve" they followed was square/cube root¹; that is, real world hardware obeys the laws of physics.
My googling dug up [1], but I'm not sure if that's it or not.
My university schooling was pretty straightforward about memory access not being O(1). We also went over adding two numbers together (also not O(1)), but these are just generally elided for brevity's sake; I don't think most of us want to start worrying/optimizing for CPU caches prior to it being a thing that perf testing says we need to worry about.
> 16/32 bit pointers for small arrays?
It's not about the size of the array, it's about the location in memory. If you're storing an index, then sure, knock yourself out.
[1]: http://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html
¹I'm a software engineer, not a physicist.
Re: WTF Is Big O Notation?
#46This seems like a good time to bring up one of my pet peeves about big O notation. Every theoretical model I've ever seen says that indexing into n bits of memory takes O(1) time. That's obviously impossible: - The pointer you need to read is log(n) bits. - The physical memory is at best O(n^(1/3)) distance away from the CPU, and thus takes that much time to get back to you. In reality it's probably O(n^(1/2)) becaus…
In academia, you usually see O(log n) for addressing. Since it doesn't really seem to matter for real-world performance, we just assume it's O(1) in practice.
Re: WTF Is Big O Notation?
#47This seems like a good time to bring up one of my pet peeves about big O notation. Every theoretical model I've ever seen says that indexing into n bits of memory takes O(1) time. That's obviously impossible: - The pointer you need to read is log(n) bits. - The physical memory is at best O(n^(1/3)) distance away from the CPU, and thus takes that much time to get back to you. In reality it's probably O(n^(1/2)) becaus…
Well, it's "wrong", but there's the saying that all models are wrong, but some are useful. If time complexity analysis had to include physical distance, then it would perhaps be less wrong, but also much less useful.
That said, "time complexity" is a bit of a misnomer anyway. It's often implied, but underneath, there is a specific operation. For example, when we say that merge sort is O(N lg N), we mean in number of comparison operations.
Re: WTF Is Big O Notation?
#48Earlier quoted context omitted.
Well, as written, it is 'O(1)'. Or did you mean to put N instead of 1000?
The inner loop is log(N), it halves the value of J after every iteration. The "do something" was meant to stand for a constant time operation so that it's N log N. But my point was really that if you told an interviewer that it was O(N^2) simply because it contained nested for loops it would be a very clear sign that you didn't fully grasp Big O.
Nah, every algorithm that is O(N logN) is also O(n^2). That would be a sign, that you as an interviewer didn't fully grasp Big O.
Re: WTF Is Big O Notation?
#49My experience, as someone who isn't a professional full-time developer (systems engineer / devops focused), but who personally geeks out on CS theory, is I find it fairly rare for developers that I work with that think of Big O considerations when writing their code. A prime example, was a piece of code that has to process incoming results that get stuck in a transnational database table. Instead of selecting, then p…
> I find it fairly rare for developers that I work with that think of Big O considerations when writing their code.
Every time I choose between a set and a vector in code, I'm essentially drawing on my knowledge of their big-O properties to choose the right one for whatever task I have at hand.
I wouldn't say that's the only piece of CS theory I use, either. I routinely run across problems that are best modeled as DAGs (any dependency relationship between items boils down to this quickly). I use DB theory any time I design a database table. I draw on language theory to write parsers.
Most of it is reflexive, I think, at this point, but it doesn't change that a "vector" is the right structure b/c I don't need O(1) lookup, or I'd like indexing.
Re: WTF Is Big O Notation?
#50This seems like a good time to bring up one of my pet peeves about big O notation. Every theoretical model I've ever seen says that indexing into n bits of memory takes O(1) time. That's obviously impossible: - The pointer you need to read is log(n) bits. - The physical memory is at best O(n^(1/3)) distance away from the CPU, and thus takes that much time to get back to you. In reality it's probably O(n^(1/2)) becaus…
In academia, you usually see O(log n) for addressing. Since it doesn't really seem to matter for real-world performance, we just assume it's O(1) in practice.
You're probably seeing a different part of academia than I am. The portions of CS academia I'm familiar with don't do O(log n) addressing.