# Tag Info

11

What is meant by "lower bound" in this case is a lower bound on the worst-case number of comparisons. In this case, it happens to also be an upper bound. The lower bound has to be something that is true for every possible N and every possible combination of elements in both arrays, right? 2*N* - 1 seems more like it would be the upper bound since there is ...

9

Is it true that every algorithm with runtime complexity of $T(n)=\Omega(n)$ satisfies that $T(n)=\Theta(f(n))$ for some convex function $f$? No. A simple example is $$T(n)=\begin{cases}n & \text{ when } n \text{ is odd,}\\ n^2 & \text{ when } n \text{ is even.} \end{cases}$$ What if we also require $T(n)$ be strictly increasing? The answer is ...

8

If every $k$th operation takes $O(\log n)$ time, then the best bound you can get on the amortized complexity is $O(1 + \frac{\log n}{k})$. This follows from the definition of amortized complexity.

6

The authors meant "show that any algorithm makes at least $2N-1$ comparisons in the worst case". See Toms answer and comments for an explanation.

5

Each time add $i$ to $s$ and increase $i$ by one, up to reach to $n$. Hence, if you find the $k$ such that $s = 0 + 1 + 2 + ... + k$ be equal to $n$, you can find the number of running loop. As $1 + 2 + \ldots + k = \frac{k(k+1)}{2}$, you need to solve this equation $\frac{k(k+1)}{2} = n$. $$k^2 + k -2n = 0 \Rightarrow k = \frac{-1 + \sqrt{1+8n}}{2} = \... 4 The average case running time of quicksort satisfies the recurrence$$ T(n) = \frac{1}{n} \sum_{i=1}^n [T(i-1) + T(n-i)] + \Theta(n), $$with base case T(0) = \Theta(1). In view of solving this recurrence, let us replace \Theta(n) with n+1 and \Theta(1) with 2 (the reason for these specific choices will become apparent below). Changing the order ... 4 Let's consider the outer two loops first. For a fixed value of i, the number of iterations of the middle loop is exactly n-1 - (i+1) + 1 = n - i -1. Since i ranges from 0 to n-1 (in the outer loop), the overall number of iterations of the middle loop is:$$ \sum_{i=0}^{n-1} (n - i -1) = \sum_{i=0}^{n-1} i = \frac{n(n-1)}{2}. $$For each of those ... 3 The most common approach is to take the longest number, and divide it in half (rounding an odd number of digits arbitrarily). So for x = 12345 y = 2478 you would get a=12, b=345, c=2, d=478. Since the number of digits in x is not even, we are free to choose whether to split into a=12 and b=345 or a=123 and b=45; it makes no difference to the running time. ... 3 Since you're not guaranteed anything about the order of the input, it's possible that the n/2 position has the smallest/largest element of the input. Then quicksort will proceed and put everything else on one side of the pivot. 3 Yes. There are problems where we can prove there is a \Omega(\lg \lg n) factor slowdown. We also know that the slowdown is at most O(\lg n) in all cases. See What classes of data structures can be made persistent?. 3 There is an O(k) algorithm [1]. [1] Frederickson, G. N. (1993). An optimal algorithm for selection in a min-heap. Information and Computation, 104(2), 197-214. 3 There is no one true answer. It depends on context. The most common context is one where polynomial-time is taken as more or less synonymous with efficient, so if you had no further context, I would certainly guess "polynomial time". Polylogarithmic time is used only in very narrow contexts. In general, if you think your audience might not be sure about ... 2 Here is an O(k\log k) algorithm at this SO answer, slightly improved. Create toVisit, a collection of nodes that contains the nodes which we will traverse next. This is initially just the root node. Let counter c = 1. While c < k: Remove the smallest node from toVisit Insert that node's children in the given min-heap to toVisit Return the ... 2 So you have the right logic, if you have a loop of O(n) iterations, the complexity of the entire loop will be O(n*\text{complexity of loop operations}). In this case, you again are correct that your loop's complexity is O(n) for each iteration. Your last bullet point shows that you understand this as well, as the total loop complexity is then O(n^2)... 2 It all depends on what hash function you are using for your strings. The worst case for Rabin-Karp would be a case in which every single substring of the text has an equal hash to the pattern, therefore every single substring would be compared and the algorithm is equivalent to brute force. The first example would be an example of this since the pattern ... 2 The running time of both BFS and DFS are \Theta(V+E) since both of them are guaranteed to visit every vertex and every edge at least once. Note that we are talking about the situation when the input graph is a connected graph whose edges are given by adjacency-list, the most common situation (in the course of your study). It is not surprising that the ... 2 As mentioned by Bryce Kille in the comments, superlinear is what you are looking for. From Wiktionary: (mathematics) Describing a function that eventually grows faster than any linear one (By the way, the first phrase in your question strikes me as rather odd: "[...] I want to refer to a group of algorithms that are mostly polynomial-time, but one ... 2 The value of i at the k'th iteration (starting from zero) is i_k := 2^k. The inner loop runs i_k times, for a total of i_0 + i_1 + \cdots + i_K, where K is the largest number such that i_K \leq n, that is \lfloor \log_2 n \rfloor. Therefore the running time is$$ \sum_{k=0}^{\lfloor \log_2 n \rfloor} 2^k = 2^{\lfloor \log_2 n \rfloor + 1} - 1 ...

2

I just found the answer myself. In this paper: Lyle Ramshaw, Robert E. Tarjan (2012). "On minimum-cost assignments in unbalanced bipartite graphs‏". Technical reports, HP research labs. in section 5, the authors show that the Hopcroft-Karp algorithm in fact solves the following problem: given an integer $s$, find matchings with $1,\ldots,s$ edges. The ...

2

I think in this case we should pad with zeros up to an even degree of the largest of the two numbers. Suppose that $x \ge y$ and $2^n \le x < 2^{n+1}$. Then one should represent $x, y$ as $$x = x_1\cdot 2^{\lceil \frac{n}{2} \rceil} + x_2, y = y_1\cdot 2^{\lceil \frac{n}{2} \rceil} + y_2$$ and then apply Karatsuba Rule. The total complexity is still $O(... 2 For all$n\geq 1$,$56n^2+106n+48> 56n^2> n^2$and$\log (264n^2+200)> \log 264n^2>\log n$, so $$(56n^2+106n+48)\log(264n^2+200) > n^2\log n\,,$$ i.e., you can take$c_1=1$. Also for all$n\geq 1$,$56n^2+106n+48\leq 56n^2+106n^2+48n^2 = 210n^2$and, for all$n\geq 200$,$264n+200 < 265n$so$\log(264n^2+200) < \log 265n^2 = 2\log n + \...

2

$\sum_{i=1}^k 2^i=\Theta(2^k)$ and you have $k\approx\log n$, so the sum is $\Theta(2^{\log n})=\Theta(n)$.

2

Let $x = \log n$ and $Q(x) = T(2^x)$. You can rewrite your recurrence as follows: $$Q(x) = T(2^x) = T(n) = T(n^\frac{1}{2}) + c = T(2^{x/2}) + c = Q(x/2) + c.$$ Which is easily solved using, e.g., the Master Theorem to obtain $Q(x) = \Theta(\log x)$. Substituting back: $$T(n) = Q(x) = \Theta(\log x) = \Theta(\log \log n).$$

2

It is $O(\log^2 \frac{\text{dividend}}{\text{divisor}})$. The inner loop clearly takes at most $O(\log \frac{\text{dividend}}{\text{divisor}})$ time since initially $k= \text{divisor}$ and it is doubled at every iteration. The outer loop requires at most $O(\log \frac{\text{dividend}}{\text{divisor}})$ iterations since the inner loop subtracts from $\text{... 2 I believe a hashing approach should give you$O(N)$time, where$N$is the length of the longer array (we can relax the constraint that they are the same size). Simply put all the elements in the first array into a hashset, and then check whether each element in the second array exists in the hashset. You could even account for duplicates by instead using ... 2 Try it like this: "we can pick a constant$C$such that, for sufficiently large$n$,$T(n)$will always be less than$Cf(n)$". Intuitively, this does indeed mean that lower-order terms and constant factors don't matter. Because lower-order terms stop mattering once$x$gets sufficiently large, and constant factors can be cancelled out by an appropriate ... 2 The RAM makes use of direct-memory-access, briefly this means that An element of data or instructions (such as a byte or word) can be directly stored or retrieved by selecting and using the locations on the storage media. Now this can be happened with the use of a DMA controller, which bypasses CPU to transfer data directly between I/O device and ... 2 We can write each permutation of$1,\ldots,n$in cycle notation, which will help us understand the behavior of the algorithm. Suppose that$i = 1$. If$1$is a fixed point, then the algorithm simply moves on. Otherwise, suppose that the cycle involving$1$is$(1\;a_2\;a_3\;\cdots\;a_\ell)$, which means that$a_2 = A[1]$,$a_3 = A[2]$, ...,$a_\ell = A[a_{\...

2

If you look at the code, it is quite obvious that there are exactly fib(N) - 1 additions. Therefore the time complexity is $\Theta(fib(n))$.

2

In my opinion the problem statement seems poorly posed. It's not clear what is meant by the problem statement. Normally, if we write $a$ or $b$ the assumption is that they are a constant: they do not depend on $n$. If they are intended to be a function of $n$, then they should be written as $a(n)$ or $b(n)$. Since that wasn't done, the only assumption I ...

Only top voted, non community-wiki answers of a minimum length are eligible