# Tag Info

### Can quantum computers be modelled as a classical computer with access to an oracle?

Let me add to the previous questions that BQP capture the power of quantum computers for decision problems, but there are other algorithmic tasks to consider. It is a reasonable conjecture that ...
• 131
1 vote

### Is $m \log^2 n$ complexity too much?

Suppose there are $m$ elements in a sequence containing $n$ distinct elements, and the distinct elements are stored in an AVL tree. Then, each of the $m$ Lookups will take $O(\log n)$ time. Each of ...
• 1,005
1 vote

• 4,048
1 vote

### Delete consecutive characters and add zeros at the end with a restriction

Have a write index. Then go through the array, identify and measure each streak of equal characters. Streaks shorter than 3 get written. At the end, write zeros at the remaining indices. Python ...
• 328
1 vote

### Delete consecutive characters and add zeros at the end with a restriction

While waiting for your updated post that includes your solution, I have posted mine: Solution A substring is deletable if all its characters will be deleted based on your requirement. This substring ...
• 1,257

• 32.8k
1 vote

### What is the lower bound on retrieving an item in a collection if no arrays(Random access memory) are allowed?

@D.W. what if at each step, there is not a fixed finite number of choices, rather some $k$ choices. In that case, there would be $O(k^t)$ different control-flow paths. By properly tuning, $k$ and $t$ ,...
Accepted

### What is the lower bound on retrieving an item in a collection if no arrays(Random access memory) are allowed?

Without arrays, $\Omega(\log n)$ time is needed. Without arrays, the memory address you access is entirely determined by the control-flow path, i.e., the sequence of control-flow decisions (if ...
• 140k

### Help with model answer for time complexity

Observe that after index is incremented from n to n+1 by line 6, the condition in line 3 is tested one last time (this condition evaluates to False because index=n+1, which is not <=n) before the ...
• 1,005

### Help with model answer for time complexity

The number of iterations of the body of the loop is $\max(0,n-1)$. The number of comparisons performed at line $3$ is $\max(1,n)$. For both, best case and worst case are identical. If the answer sheet ...
• 3,222
Accepted

• 6,942
1 vote

### Is it faster to use Counting Sort to lexicographically sort characters in a word in Python?

Asymptotically, it doesn't matter if you have very long or short words, counting sort would take more space and time if the range in which those words lie is very large, since you will have to store ...
• 330
1 vote
Accepted

### Cost of increasing a binary counter with a starting value n times

Aggregate method $\def\C{\mathcal C}$ The $i$-th bit is flipped every $2^i$ steps. Imaging the counter was increased from $0$ to $b$ and then from $b$ to $b+n$. The total cost of all $n+b$ increments ...
• 32.8k

### I need help finding the complexity of an algorithm

The base-2 iterated logarithm function $\log^*(n)$ is the number of times you need to apply the logarithm function to obtain a value that is at most $1$. It is a very slowly growing function. The ...
• 1,005
Accepted

### Understanding time complexity of algorithm to determine if parenthesis are matching

Two algorithms can have the same (asymptotic) time complexity but differ in their space complexity. The amount of extra storage space consumed by the algorithm is another performance measure of the ...
• 1,005
Accepted

### Recursive algorithm for adding numbers from 1 to n with O(1) time complexity

The sum $1+2+3+\cdots+n$ is equal to $n(n+1)/2$; hence, the following function would return the same output: ...
• 1,005

### Applying the Master's Theorem

You are right that there are on the order of $\log n$ terms in the sum and that each term is $n^2$ times a constant; however, the upper bound $O(n \log n)$ thus obtained, while correct, is not ...
• 1,005

• 3,222
1 vote
Accepted

### an O(m+n) algorithm to decide whether a graph can be reduced to a single edge with two vertices

The Simple Idea Keep the graph without multi-edges by B-operations. Apply C-operation whenever we can, keeping track of possible new opportunities of C-operations in a set of vertices. A Simple ...
• 32.8k

Top 50 recent answers are included