New answers tagged

1

The cost of adding one item at the end of the array of size n can be as large as O(n), but usually is much faster. That's why we use the term "amortized time". The work you did to add item #512 pays back for items 513 to 1023. It is "amortized". The amortized cost per items is O(1), since the cost of adding n items individually is O(n). There are various ...


0

The $i$-th time the array is split, it is split into into two arrays of size $2^{-i} n$ elements each (assuming, for simplicity, that $n$ was a power of $2$). At the ($\log n$)-th recursive call, the total space occupied by all these arrays is $$ 2n \sum_{i=1}^{\log n} 2^{-i} \le 2n \sum_{i=1}^{\infty} 2^{-i} = 2n. $$


0

Yes, you can implement merge sort inefficiently, but you don’t have to. If you sort an array, notice that you don’t need to create any copies while splitting into subarrays. You only need two integers to identify each of them. Combined with the fact that the number of nodes in the recursion tree is $O(n)$, this gives you $O(n)$ bound on space.


2

The evaluation is easier for postfix-notation expressions. The evaluation is done easily using a stack. The expression is processed from left to right, one token at a time: * operand - put it on the stack; * operator - get from the stack the number of values it needs (two for +, three for ?:, one for unary - and so on), combine the values using the ...


7

As Yuval has noted, this way of randomly generating recursive data structures is known to (usually) end up with an infinite expected size. There is, however, a solution to the problem, that allows one to weigh the recursive choices in such a way that expected size lies within a certain finite interval: Boltzmann samplers. They are based on the ...


11

Your process is a textbook example of a branching process. Starting with one $E$, we have an expected $3/2$ many $F$s, $9/4$ many $T$s, and so $9/8$ many remaining $E$s in expectation. Since $9/8 > 1$, it is not surprising that your process often failed to terminate. To gain more information, we need to know the exact distribution of the number of $E$-...


3

The brute force solution enumerates all permutations. You can easily encode each permutation using $n\log n$ bits, since you can encode it as a list of numbers from $1$ to $n$, and each number takes $\log n$ bits to encode. You can check that a given permutation corresponds to a tour using $O(\log n)$ additional bits of space, so in total the space ...


2

It's rarely possible to prove that an algorithm is optimal. You would have to show that your algorithm takes n steps, and for some reason solving the problem in less than n steps is impossible. Even for someone who is 100 times more intelligent than you and me together. An example is finding the maximum of n random numbers, which can done in n steps, and n ...


1

Approach 1 For example, consider the two orders: 1, 2, 3, 4, 5 and 2, 4, 1, 5, 3. According to your approach, we will get a cycle 1->2->3->4->1. We then remove 3->4 and 4->1, and obtain a graph: ______ / \ 1->2->4->5->3 \______/ Now 5->3 and 1->2 respectively violate the first and the second orders, so we remove them, and get ...


1

Is the sequence $(a_i)_{i<n}$, where $a_0=1$ and $a_{i+1}=\lceil 1,5\cdot a_i\rceil$, what you need?


0

I figured out why the runtime is O(N^2). Yes, the while loop does run N/2 times. However, that is equivalent to - "for(int i = 0; i < N; i+=2)" which has a runtime of O(N) still. I confused it with - "for(int i = 0; i < N; i *= 2)" which has a runtime of O(logN). The summation also results in the correct answer in this instance.


0

The definitions are (as used commonly in Computer Science, all functions positive): $f(n) = O(g(n))$ if there is $c_1 > 0$ such that for some $N_1$ whenever $n \ge N_1$ it is $f(n) \le c_1 g(n)$ $f(n) = \Omega(g(n))$ if there is $c_2 > 0$ such that for some $N_2$ whenever $n \ge N_2$ it is $f(n) \ge c_2 g(n)$ $f(n) = \Theta(g(n))$ if $f(n) = O(g(n))$...


2

The condition i % j == 0 is satisfied when j is equal to m * i for each m = 0, ..., i - 1. Therefore, the condition in the second loop will be satisfied i times. In form of summation this can be written as: $\sum_{i=0}^{n-1} \sum_{j=0}^{i-1} \sum_{k=0}^{j * i - 1}$ Moreover, your code is equivalent to: sum = 0 for (i = 0; i < n; i++) { for (j = 0; j &...


3

For a given $s$, you do $(|s|-1)n$ additions, not $|s|-1$ additions: you have to compute the inner sum for each $i\in [n]$. Thus, you are missing a factor of $n$.


1

If an algorithm has time complexity $T(n) \in \Theta (\log_2 n)$, then it means that $T(n)$ is bounded above and below by constant factors of $\log_2 n$ for sufficiently large $n$. This definition actually leaves a lot of room for possible $T(n)$, and the question in your textbook makes some additional assumptions (or uses a very loose definition of "...


1

Basically, the complexity of an algorithm gives the relation of the change in the running time with respect to the change in the input size. You can think it as, $log_2(1M)$ -> 20 sec $log_2(2M)$ -> ? sec $log_2(2M) = log_2(2 *1M) = log_2(2) + log_2(1M) = 1 + 20 = 21 sec$


1

If you check what Dijkstra's algorithm does, it computes the shortest paths to all nodes from a given start node.


0

Textbooks in algorithms are chock full with examples of algorithms, often with analysis. For example, take a look at Erickson's "Algorithms", Dasgupta et al "Algorithms". Looking around for lecture notes will get you a lot of others. Analysis of algorithms requires some specialized techniques, a modern overview is Sedgewick and Flajolet's "Introduction to ...


2

If you check the definitions, big-O means "bounded from above" (with a fudging constant $c$ multiplying it all, starting at a high enough $n$), you can disregard "constants multiplying" and "slower growing terms"; so you can say: $\begin{equation*} 5 n^2 \log n - \dfrac{100 n^2}{\log_4 n^2} + 40 = O(n^2 \log n) \end{equation*}$ (could also say $O(n^3)$,...


3

Of course, it is true. However, it is not a property of Dijkstra's algorithm but is property of the shortest paths themselves. Suppose that is not true, and you have a shorter path from $C$ to $B$, we denote it as $p_{CB}$. Then we would have a path $A \rightarrow p_{CB} \rightarrow F \rightarrow E$ from $A$ to $E$ which is shorter than $A \rightarrow C \...


1

Your algorithm has O(n^2) worst case complexity. You have a for loop of O(n). Inside your for loop you have a while loop which is O(currentNum). So if your currentNum is O(n) (ex nums[i] = length.nums for each i) then the complexity is O(n*n) = O(n^2). Hint Try not to recalculate things. You could use Dynamic programming technique. You need: def canJump(i)...


Top 50 recent answers are included