# Tag Info

Accepted

### Asymptotics of the sum of a geometric series

There is an abuse of notation in your question: you are using $i$ as both the index for the summation and as the total number of terms in the sum (in the closed formula). Anyway, the ratio of the ...
• 29.5k

### Assuming constant operation cost, are we guaranteed that computational complexity calculated from high level code is "correct"?

Yes, this is reasonable as a first cut approximation. As always, there are caveats. A theoretical model is a model. It is used for making predictions, but models typically are not perfect, and there ...
• 159k
Accepted

### Possible Mistake in Skiena's Algorithm Design Manual

You are totally right, though I think there is an easier proof: if $m = n$, then $mn-m^2 +m= m\notin \Omega(m^2)$. However, since the analysis is done when searching for a worst case, you could just ...
• 15.6k

### Big-O time complexity for this code snippet

You are right, the two innermost loops perform $\Theta(\log n)$ iterations each, so we have a total of $\Theta(\log^2 n)$ iterations, which are repeated $\Theta(n)$ times in the outer loop, which ...
• 843

• 29.5k
Accepted

### Subtracting Two same asymptotic values

I make an example: if $a=\frac{2}{\sqrt{n}}$ and $b=\frac{1}{\sqrt{n}}$, then both are $O(\frac{1}{\sqrt{n}})$ and $a-b=\frac{1}{\sqrt{n}}=O(\frac{1}{\sqrt{n}})= \Theta (\frac{1}{\sqrt{n}})$. If ...
• 843

### Asymptotic equivalence allows difference by a constant factor?

There are multiple notions/definitions of asymptotic. You need to pick one that is appropriate for your goals. One approach to asymptotics is exactly as you have stated (see, e.g., https://en....
• 159k

### Solving recurrence by iteration, choosing base case

Well, obviously $T(1),T(2),\dots,T(100)$ are all integers. So, let $c=\max(T(1),T(2),\dots,T(100))$. $c$ is obviously some integer, so it is a constant. So yes, all of those base cases are at most ...
• 159k
Accepted

### How are pointers modeled on bit-based computer models?

It sounds like you're just asking for the definition of Random-access machine, which is similarly formal to Turing machines, but formally defines how to do "indexing" operations. There's ...
• 945