New answers tagged

0 votes

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 ...
user avatar
  • 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 ...
user avatar
1 vote

Time Complexity of Exponentiation Operation as per RAM Model of Computation

I just want to say first that I'm not an expert, but I find this question interesting. I will focus on integer exponentiation. Like the OP says, intuitively, exponentiation of integers should cost $O(...
user avatar
1 vote
Accepted

Complexity of a restricted SAT problem

Repeatedly perform the following simplification procedures: If a variable appears only once, we can satisfy the unique clause containing it by setting the variable accordingly. Therefore we can ...
user avatar
3 votes

Exponential Time Hypothesis and the input size vs number of variables

ETH says that, for $s_k = \inf \alpha$ such that k-sat can be solved in $2^{\alpha n}$, it holds that $s_3 > 0$. The strong exponential time hypothesis (SETH) says that $\lim\limits_{k \rightarrow \...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 1,257
0 votes

Examples of time complexity $O(n^k)$

In parameterized complexity, the class XP contains all problems that can be solved in time $O(n^{f(k)})$ where $k$ is the size of the parameter, and $f$ is some computable function. Note that ${n \...
user avatar
0 votes
Accepted

Time complexity analysis for dynamic programming using memoization

The time-complexity of dynamic-programming with memoization Here is the simple principle. Suppose an algorithm applies dynamic programming to solve a problem, with the majority of running time spent ...
user avatar
  • 32.8k
1 vote

Complexity of finding $d$ largest eigenvectors of a symmetric matrix

The power method takes $O(n^2)$ time per step. It is an iterative algorithm, and convergence is geometric. The absolute speed of convergence depends on the ratio between the two largest eigenvalues. ...
user avatar
  • 18.7k
4 votes
Accepted

Finding Median value given a tuple (value, frequency) in O(n) worst case time complexity

I think you can still use the linear time selection algorithm (median of medians) here. Let's call this algorithm $Select$ and let the median position be $m$, which is initially equal to $n/2$.Recall ...
user avatar
  • 1,257
1 vote

Finding Median value given a tuple (value, frequency) in O(n) worst case time complexity

If the pairs are given ordered by increasing salary, it suffices to compute the prefix sum of the frequencies $F_k:=\sum_{i=1}^k f_k$ and find the sum closest to the half of the total. If the pairs ...
user avatar
  • 3,222
0 votes

Averege time complexity of open addressing

Implementations will typically store the hash value inside the table - this will save lots of hash value calculations. For the hash value of the key being looked up, it depends on the caller how often ...
user avatar
  • 24.9k
1 vote
Accepted

Averege time complexity of open addressing

Define the load factor of a hash table with open addressing to be $n/m$, where $n$ is the number of elements in the hash table and $m$ is the number of slots. It can be shown that the expected time ...
user avatar
2 votes

equivalency of some facts in $O$ notation

Let $a>b>0$. From $\log(a+b)=\log(a)+\log\left(1+\dfrac ba\right)$, we draw $$\log(a)\le\log(a+b)\le \log(a)+\log(2)$$ and similarly for $b>a$.
user avatar
  • 3,222
2 votes
Accepted

Subdivide a graph into non-crossing triangles with maximum edge weight

With proper classification and memoization, an approach by dynamic programming runs in $O(n^3)$ time, where $n=|V|$. That seems efficient enough considering there are $n(n-1)/2$ edges. Assume $n\ge 3 ...
user avatar
  • 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$ ,...
user avatar
5 votes
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 ...
user avatar
  • 140k
0 votes

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 ...
user avatar
0 votes

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 ...
user avatar
  • 3,222
2 votes
Accepted

Find a path with given weight and the minimum number of edges on a tree

This answer explains an algorithm that finds the minimum number of edges in $O(n\log n)$ time. With more bookkeeping, the path of weight $k$ with that minimum number of edges can also be found in $O(n\...
user avatar
  • 32.8k
4 votes
Accepted

Count the number of intersections of n chords of a circle in O(n log n) time

Fix an arbitrary point on the circle. For example, $p_0$. Each line segment from $p_i$ to $q_i$ can be represented by a pair of numbers $(a_i, b_i)$, where $a_i$ is the clockwise circular distance ...
user avatar
  • 32.8k
2 votes

Asymptotic Analysis of T(n) = 2T(n/8) + 2T(n/4) + n

Let $n=2^m$. The recurrence is written $$T(2^m)=2T(2^{m-3})+2T(2^{m-2})+2^m$$ or $$U(m)=2U(m-3)+2U(m-2)+2^m.$$ A particular solution is given by $U=c2^m$ and more precisely $$c=2\frac c8+2\frac c4+1,$$...
user avatar
  • 3,222
5 votes
Accepted

Asymptotic Analysis of T(n) = 2T(n/8) + 2T(n/4) + n

You are right: you can apply the Akra-Bazzi method to find that $T(n) \in \Theta(n)$. Your professor is right: since $\Theta(n) \subseteq \mathcal{O}(n\log n)$, it is also true that $T(n) \in \mathcal{...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 32.8k
0 votes

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 ...
user avatar
0 votes
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 ...
user avatar
0 votes
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: ...
user avatar
0 votes

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 ...
user avatar
0 votes

Determining Big O of a for loop nested within a while loop

Your answer of $O((\log n)^2)$ is incorrect because the cost of each iteration is not $O(\log n)$; for example, the cost of the first iteration is proportional to $n/2$. Your friend’s answer $O(n \...
user avatar
2 votes
Accepted

Why do hash tables have no access/indexing complexity but have $O(1)$ search complexity?

I think you have interchanged the idea of index and search. Access/index here means given a position or index, like in an ordinary array or list, return the element in that index. This is why arrays ...
user avatar
  • 1,257
2 votes

Efficient data structure to maintain a set of postal codes and mailbox numbers

Your idea of using a tree of tree representation seems good. Let $n$ be the current number of postal codes and $m$ be the current maximum number of mailboxes in any postal code. Then the ...
user avatar
  • 1,257
3 votes
Accepted

Comparing two functions rate of growth

$$\lim_{n\to\infty}\frac{n^2}{\log(n)\ 3^{\log(n)}}=\lim_{n\to\infty}\frac{n^{2-\log(3)}}{\log(n)}=\infty$$ because any positive power of $n$ grows faster than a logarithm. To convince yourself, you ...
user avatar
  • 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 ...
user avatar
  • 32.8k

Top 50 recent answers are included