5 ms·
> Now we can make an assumption that the int it's a finite number say u32, this means we can construct a binary tree with a depth of 32 with access time of O(32
by jemfinch 3y ago
> Now we can make an assumption that the int it's a finite number say u32, this means we can construct a binary tree with a depth of 32 with access time of O(32) therefore O(1) time and space.
Heck, let's go even further. All the computers I've used have a fixed amount of memory, addressable by a u64, so I guess all my algorithms are constant time now.
I guess we've solved the interview, folks.
- josh-sematic 3y agoYeah, my curiously disappeared when I read this line.
- burntsushi 3y agobig-O notation isn't some fundamental secret of the universe. It's a model devised by humans, and typically used in the context of real world computers as a means for conveying an understanding of how algorithms scale. If we considered the bits of integers as the smallest unit of work in all cases (it is of course relevant to consider bits as the unit of work in some cases), then big-O notation becomes a lot more tedious without typically adding more value. See: https://cs.stackexchange.com/questions/140642/silly-question-what-counts-as-a-unit-of-work-when-computing-big-oh-time-compl https://cs.stackexchange.com/questions/140642/silly-question...
- remram 3y agoStill it's a notation that had meaning, about the behavior as n goes to infinity. If you take out n, or if you don't have an n, just don't use it.
- burntsushi 3y agoWhat? Saying something takes O(1) time or space is absolutely meaningful. https://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions https://en.wikipedia.org/wiki/Big_O_notation#Orders_of_commo...
- okl 3y agoSetting n=1 to say your O(n) is actually O(1) makes no sense because big O notation tells us how the time/space grow as function of the input size. If n=1, input size is fixed.
- burntsushi 3y agoThat's not what is happening here. The n cannot grow because the representation is fixed. Read the links I've provided. The convention and meaning are clear here.
- remram 3y agoO notation has meaning if something is 'n' and that 'n' can grow. Without an n defined somewhere, nothing can be O(n), nothing can be O(1).
- burntsushi 3y agoI think the links I've provided sufficiently explain what the common convention is. And in the context in which the notation is used here, it is crystal clear what is meant. This feels to me like errant niggling for the sake of it.
- remram 3y agoFrom your link (emphasis mine): > In each case, c is a positive constant and *n increases without bound* It is indeed crystal clear what "asymptotic" means. If you have a definition for O-notation in non-asymptotic contexts, I have never heard of it.
- burntsushi 3y agoI no longer understand where your confusion is, so I'm not sure how to respond. I'd suggest taking it back to what was actually said in the OP and the criticism it got. Otherwise, if you're arriving in ridiculous places like "you must be trying to say that O-notation is used in non-asymptotic contexts," then there's very clearly some kind of miscommunication or misunderstanding. From my perspective, your comments are terse, unclear and not addressing the central point directly.