# Tag Info

• 111

### Array access is O(1) implies a fixed index size, which implies O(1) array traversal?

Big-O notation can be tricky because it hides details. Big-O describes a way to measure a function related to complexity. That function may be "number of memory accesses," which would ...
• 3,085

### Array access is O(1) implies a fixed index size, which implies O(1) array traversal?

The cost of array access would be for example $c_1$ if the array size is less than $2^{64}$, $c_2$ if the array size is less than $2^{128}$, $c_3$ if the array size is less than $2^{256}$ and so on. ...
• 25.2k
Accepted

### Array access is O(1) implies a fixed index size, which implies O(1) array traversal?

It's a good question. From a pragmatic perspective, we tend not to worry about it. From a theoretical perspective, see the transdichotomous model. In particular, a standard assumption is that there ...
• 141k
1 vote
Accepted

### Simulating nondeterministic RAM with nondeterminstic turing machine

Here is your hint. Imagine that we augment $P$ to record a log of all the random-access reads and writes $P$ does to memory (i.e., for each read, record the address and the value that was read; for ...
• 141k
Intuitively : Number of nodes in last level is more than sum of all nodes in Previous level. At Level-$\color\red0$, we have $1$ node. It can be written as $b^\color\red0$ At Level-$\color\red1$, we ...