# Tag Info

0

Yes, you are correct. Essentially, since you are dealing with a circuit, the graph representing it is a DAG (directed acyclic graph). Hence, your implementation will indeed compute the value of each node, and will visit each node not a lot of times (usually it will be the "number of children$+ 1$", as in your recursive case), so it won't be hard to ...

0

I got it: this algorithm has a nearly-constant complexity, specifically the complexity is $\Theta(\log^{*}(n))$ where $\log^{*}(n) \le 5 \ \forall n \le 2^{16}$

0

I'll keep your terminology of $n$ being the number of routes, $N$ being the average length of a vector, and $k$ being the sum of the lengths of all vectors. Then $N = k/n$. Your first approach it's implying that the cost of merging can be assumed to be $O(N)$, but this is only true at the beginning; when you're approaching the end of the process, the average ...

1

You can easily compute the height $h$ and the total number of nodes in the recurrence tree. After $h-1$ levels, the size of the subproblem is at least $k$ and at most $2k$. Therefore, $n/2^{h-1} \geq k$ after $h-1$ levels. Thus, we get the height of the tree at most $\log (n/k)+1$. Furthermore, the total nodes in the recurrence tree is at most $O(2^{\log n/k+... 0 Denote by$T(n)$the number of comparisons on a list of length$n$. Then$T(0) = 0$,$T(1) = 1$, and $$T(n) = n + T(x) + T(n-1-x) + x(n-1-x)$$ for some value of$x$that could depend on the array. Let us prove by induction that$T(n) = n(n+1)/2$, whatever$x$is. This holds when$n = 0$and$n = 1$. For$n > 1$, we have $$T(n) = n + \frac{x(x+1)}{2} + \... 1 If the output of the algorithm takes exponential space, then any algorithm must take exponential time. It takes at least N steps of computation even to output N characters (even ignoring the time it takes to figure out what to output), so the length of the output is a lower bound on the running time of the algorithm. 2 The kind of algorithm that you consider can be formalized in the algebraic decision tree model. In this model, there is an \Omega(n\log n) lower bound on solving the set intersection problem, which is equivalent to your problem. See for example lecture notes of Jeff Erickson. -1 In a hash table, we take the key, and then from the key we calculate at which place in the table it should be stored. So you just look at that single place, and usually that's where the key is stored. It's a bit more complicate. Since there are more possible keys than entries in the table, there must be keys that "should" be stored in the same ... 1 You can use quickselect, which has expected linear time complexity. (There's a version using the median-of-medians partitioning algorithm which has worst-case linear time complexity, but it's usually a lot slower in practice.) Note that if there are duplicate elements in the two arrays, it might not be possible to satisfy the strict less-than constraint ... 2 The thing is, a hash table opens the "book" exacty (or at least close by, in some terms) where it needs to. The better analogy is like accessing a list of values with an index: If you have a book list of 100 people and their phone numbers, and you want the 37'th person's number, you know exactly where to search it in the book - you don't have ... -1 Concatenate A and B into one array C with a total length of 2n. You start with the partition [1, 2n] of C with the goal to make the first l items less than the last r items, l = r = n initially. As long as your partition has length 2 or more: Pick a random pivot element. Partition into two partitions of length x and y, like in quick sort. If x <= l then ... 0 I made a mistake in my question. Since order does not matter the complexity is simply n*m where n is the amount of days and m is the amount of items. Since this drastically reduces the complexity I consider this an answer. I will leave this open if others can provide an optimization. 1 You could sort them and then iterate over them. Sorting is nlogn and then it would only take one more pass to go check them because once you've passed an element, you know you've done all the swapping you need for that element. 1 There will be no contradiction, since D doesn't run in time n^{1.4}. In fact, what the proof of the time hierarchy theorem shows is that no equivalent Turing machine can run in time n^{1.4}, precisely because this will result in a contradiction. In other words, the language computed by D lies outside of \mathrm{DTIME}(n^{1.4}). On the other hand, ... 1 The analysis questioned in Problem 3 assumes(?) an implementation closer to ACM Algorithm 64 than to what Sedgewick is getting at (as does "Problem 1"): recursion on all partitions, not "iteration on the biggest one". 0 Your teacher is correct. We measure the complexity with respect to the input's size. Here, you don't have any input to the function, and n is just a constant defined within the function. Thus, the loop runs only a constant number of times, which is O(1). 1 For quick sort, you end up with quadratic runtime only if you use the most stupid method of picking a pivot- by taking the first or last element. Picking the middle element, or the median of first, last and middle element, it will run nicely fast because for all except 2k elements we have just comparisons, and nothing will be moved. Still n log n, but with a ... 1 In my_func(a), Recurrence Relation will be T(n) = \begin{cases} 4T\bigg(\frac{n}{2}\bigg)+{n} & \quad \text{if } n \geq 4\\ 1 & \quad \text{if } n <4 \end{cases} In new_func(a), Recurrence Relation will be T(n) = \begin{cases} 3T\bigg(\frac{n}{2}\bigg)+{n} & \quad \text{if } n \geq 4\\ 1 & \quad \text{if } ... 1 O(n^2\log n) is better, since \lim_{n \to \infty} {n^2\log n \over n^{2.32}} = 0. 1 O(n^{2.32}) is kind of unusual. Do you have a mathematical proof for this, or is it an estimated based on observations? In that case, you can't draw any conclusions from it. Big-Oh is an upper bound. So first you need to check what is the actual behaviour. If an algorithm runs in O(n) then it is correct (but not very useful) to say it runs in O(n^{2.32}... 1 I see, that answer is done and accepted, but let me share some thoughts: Short answer: knowing only upper bounds it's impossible to compare algorithms. We can compare upper bounds, but this doesn't give answer to algorithms relation. Long answer: assume we have f\in O(n^2\log n) and g \in O(n^{2.32}). Because \exists N \in \mathbb{N} such that for n &... 1 You will need to compare the rate of change for both functions. This can be accomplished by taking the derivative of both functions:$$ O_1'(n^2 log(n)) = \frac{d}{dn} n^2 log(n) = n + 2n × log(n)  O_2'(n^{2.32}) = \frac{d}{dn} n^{2.32} = 2.32n^{1.32} $$Plot these derivatives and compare the graphs. If they still seem too close, continue to take higher ... 4 Your reasoning is wrong. It is in \Theta(n^{\log_2(5)}). Hence, it is also in O(n^{\log_2(5)}). Answer to the update: Also, for the update part, it is wrong. You can find it by a straightforward expansion (no need to master theorem):$$ T(n) = 2T(n-1) + O(n) = 2(2T(n-2) + O(n-1)) + O(n) \\ = 2^2T(n-2) + O(n-1) + O(n) = \cdots = \\ 2^n * T(0) + O(1) + O(2)... 0 Define S(n) = T(2^n), write down a recursion formula for S, solve it using the master theorem, and then let T(m) = S(log m). Or calculate T(n) for n = 3^0, 3^2, 3^6, 3^14, 3^30, 3^62 etc. without the master theorem, guess a formula for T(3^(2^k-2), and prove it. Let D log 3. If T(1) = c, then T(9) = 4T(1) + (log 9)^2 = 4c + 4D^2. T(3^6) = 4T(9) + 36D^2 = ... 0 A computer doesn't have trouble doing anything; it does precisely what it's programmed to do. It is efficient in doing a task if and only if we come up with an efficient algorithm for it. In that regards, we have a whole hierarchy of less and more efficient such tasks. On the bottom of the hierarchy is the problems where the machine just finishes after a ... 0 I would say the halting problem, is the hardest - single most important problem in computer science. The halting problem is an undecidable problem - meaning that no computer program can always successfully solve it and never get stuck in an infinite loop. An important implication of the halting problem, is Rice's theorem, which can prove that some ... 0 Master Theorem is for Dividing and Subtracting Function. The Master Theorem at it's core don't discuss Square Root Function. Although, some Manipulations can be done. But for the sake of simplicity, solving by Substitution Method Given,$T(n)=4T\bigg(\frac{\sqrt n}{3}\bigg) + (\log(n))^2T(n)=4T\bigg(\frac{n^{1/2}}{3}\bigg) + (\log(n))^2T(n)=4\bigg(4T\...

1

No, because you can write an algorithm with space complexity $O(1)$ that prints an unlimited amount of output. For instance, here is one while true: print('yo!') This means that the length of the output can be much larger than the space complexity, and the length of the output is not a lower bound on the space complexity.

2

The problem is still NP-hard. You can show a polynomial-time reduction from the Hamiltonian path problem on graphs of degree at most $3$.

2

The function swap is not recursive so the depth of the call stack is always constant. While it is true that the space complexity of your algorithm is $O(n)$, it is also true that it is $O(1)$ (if we don't count the size needed for the input array array). Inlining the function swap makes no difference as far as the asymptotic space complexity is considered.

0

The code takes $O(n^2)$. It is tricky to see that, since its very easy to miss the fact that if i not in sample_list takes another $O(n)$ time - just by itself. Here is the breakdown of the complexity: check_list = [] # O(1) for i in sample_list # repeats n times if i not in check_list: # takes an O(n) time to do the check check_list.append(i) # ...

Top 50 recent answers are included