[jemfinch]

> 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.

[burntsushi]

big-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...

[remram]

Still 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]

What? Saying something takes O(1) time or space is absolutely meaningful.

https://en.wikipedia.org/wiki/Big_O_notation#Orders_of_commo...

[okl]

Setting 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]

That'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]

O 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]

I 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]

From 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.

[josh-sematic]

Yeah, my curiously disappeared when I read this line.