New answers tagged

0

I can offer one simple optimizations to your code. At the moment your code will take $\Omega(n^2)$ time even on a string in which each symbol appears at least $k$ times. This can be avoided using counting sort: using a single pass, you can compute how many times each letter appears. If every letter appears either 0 or at least $k$ times, then the current ...


1

Your recurrence isn't really defined for $n = 1$. This suggests using a different value for the lower bound in the integral. The formula given by Akra–Bazzi doesn't actually depend on the exact value of the lower bound that you choose – it can at most affect the big Theta constant or, in your case, some lower order term. If you choose any lower bound which ...


3

It runs in time $O(n)$. Remember that a function only returns once. In each call to f, the for loop is immediately terminated at i=0 by the return statement, so the function body is equivalent to if n < 100000 return 0; else return f(n-1); However, your answer of $O((n!)^2)$ is not wrong: $(n!)^2$ is a huge overestimate of the running time,...


0

You want to write $n$ as $b^x + r$ with $x,r \ge 0$ and $b \in \{2, \dots, 2^{31} - 1\}$. Since you're asking for the asymptotic complexity and the base $b$ is in a set of constant size, you can just focus on a single value of $b$. The exponent is then $x = \lfloor \log_b n \rfloor$ and can be found using $O(\log \log n)$ operations (search for the first $...


2

Of course, every letter is a one letter palindrome - so let's assume you are looking for a palindrome that is at least two letters long. If your goal is just to find any palindrome in a string $\{a_i\}$(rather than finding all palindromes or finding the longest palindrome, for example) then you only need to consider two cases: 1) If $a_n=a_{n+1}$ for any $...


0

Your solution only works in the cases where the midpoint of the palindrome is the middle point of the string. You can use the more general following approach: Consider each letter of the string to be the midpoint of a palindrome. Then look to the left and to the right of the current letter and check if the characters match. If they do check if the next pair ...


0

Kth smallest number in a dynamic stream of numbers. Idea from the above source. Have two heaps, one a max heap with $k$ elements (all the elements less than the $k$th largest element and the $k$th largest element itself are here) and the rest of the elements are in the other min heap. Inserting a new element: If the new element is less than the top of the ...


2

I wouldn't overthink it: With $n$ distinct elements you have a $1/n$ chance of a match. On average you will have to look at $n/2$ elements. That's because $\sum_{i=1}^{n/2} 1/n = 1/2$. Worst case of course being that you match on the last thing you look at, so have to look at all $n$ of them.


2

The phrase "the element being searched for is equally likely to be any element in the array" is ambiguous. It might mean two different things: The element is at a uniformly random position in the array. The element is chosen uniformly at random from the set of elements in the array. This ambiguity suggests that the authors are making the hidden assumption ...


0

If the decision version can be solved in poly-time, can the optimization version be solved in poly-time as well? This depends on how technically precise you want to be. The most correct answer is "No". Consider an optimisation problem $OP$ for which the encoded length of the output is superpolynomial in the encoded length of the input. Clearly no algorithm ...


2

Assume the maximum length of strings is $k$, which is less than some constant. Here is a simple algorithm that runs in linear time and $O(1)$ space complexity. The strategy is simply counting strings by length followed by in-place rearrangement. Assume the input is an array $s[0], s[1], \cdots, s[n-1].$ Count the number of strings of length $i$. Store it ...


0

Let us start by analyzing the recursion tree of your algorithm. The depth is $2n$. As for the number of nodes, at level $k$ you have all arrangements of $a$ left parentheses and $k-a$ right parentheses such that $a \leq n$ and in each prefix of the word, there are at least as many left parentheses as right parentheses. Bertrand's formula states that for ...


1

As in the link provided by Raphael, Peter shows that Input Reversal requires $\Theta(n^2)$ time on vanilla single-tape TMs. For a decision problem, the language $$L = \{x0^{|x|}x \mid x \in \{0,1\}^\ast \}$$ also provably needs $\Theta(n^2)$ time to compute. To see this, use Peter's communication complexity argument , along with a classical result that $EQ_n$...


2

The language of all palindromes needs quadratic time on a single-tape Turing machine. See for example lecture notes of Eric Ruppert. The proof uses crossing sequences. In contrast, on a two-tape Turing machine, the language can be decided in linear time.


1

This variant decreases number of main loop passes by factor of 2, but in return loop body uses twice workload. Since the change is minor, you can simply read complexity from basic selection sort. The selection sort has this property that number of swaps is at most $n$, finding element to its proper place, so it takes $\mathcal O(n)$ swaps in the worst case. ...


3

Asymptotically, you're right: for big-enough inputs, the $\Theta(n\log n)$ algorithm can be faster. However, this is only true for big enough $n$. It might be that "big enough" means "far bigger than any actual computer can store" or even just "plenty bigger than any input I care about". For a specific example of this, look at matrix multiplication ...


2

Let $V(0)=12$ and $V(j)$ be the value of the variable $i$ immediately after the $j$-th iteration for $j \ge 1$. $$ \begin{align} V(j) &= \frac{7}{3} \cdot V(j-1)^5 \\ &= \left(\frac{7}{3}\right)^{1+5} \cdot V(j-2)^{25} \\ &= \left(\frac{7}{3}\right)^{1+5+25} \cdot V(j-3)^{125} \\ &= \dots \\ & = \left(\frac{7}{3}\right)^{\sum_{k=1}^{j-1}...


2

The definition of $\Theta$ includes two constants that the function is multiplied with, and a smallest n where the relation applies. (There is an $n_0$ such that for all n ≥ $n_0$, $c_1 g(n) ≤ f(n) ≤ c_2 g(n)$). If $n < n_0$ then anything can happen. And if one algorithm comes with much smaller constants, then it may stay faster for some quite large n. ...


0

The definitions aren't clearly given in the fragment of the book that Google showed me. Clearly, if the table has $N$ entries and each entry contains at most one item, you can iterate through all the items in time $\Theta(N)$. Now, if $N$ is some fixed constant, $\Theta(N)$ time is constant time – and the set has constant size. On the other ...


3

Treat SPG as DAG We can see easily that every path from the source to the sink in a series-parallel graph (SPG) always goes nearer and nearer to the sink. It can never go backwards. There is no sideways. For the example in the illustration provided in the question, it can never move "up". This phenomenon can be proved easily by structural induction. So we ...


2

I don't agree that the author was talking about iterating over a set with constant time per element. I've never seen iteration described in time per element. It's certainly not common enough to be an unspoken assumption. I would guess that instead it's simply an editing miss.


2

Let's build some recursive function. We start picking any vertex of the tree $T$ and call it $R$ as root. If $R$ was removed, you would get a forest of several sub-trees. Every subtree $T_k$ has a vertex $k$ connected to $R$ in $T$. Now there are 3 types of paths contributing to the sum of cost of paths $N(R)$: $I(R)$, the cost of all inner paths of the ...


1

Since I don't have enough points for a comment: This problem is not going to have a very efficient solution. Looking at the $k=3$ case should be good start. In this case one can solve this problem with $O(|E|)$ space by keeping an (online) adjacency set for each vertex and when an edge $(u,v)$ arrives comparing the adjacency sets of vertices $u$ and $v$ for ...


Top 50 recent answers are included