3

I think this is a common misconception among undergraduates about $\mathcal{O}$, $\Omega$, and $\Theta$. It is not like these symbols represent worst, best, and average case running time, respectively. They are just upper and lower bounds on running times and you can have lower and upper bounds on all of those cases. In some sense, $\Omega$ is just the ...


2

Let us denote the solution for a string $w$ and a set $A$ of remaining letters by $s(w,A)$. Also let $A = a_1 < \cdots < a_n$. If $w$ equals $>^{n-1}$ then clearly the solution is $a_n a_{n-1} \ldots a_1$. If $w$ starts with a run of $\ell$ many $>$'s (possibly $\ell=0$), then the first $\ell+1$ letters of any solution must be $a_{\ell+1} \ldots ...


2

It's a variable substitution. First, realize that in the leftmost side of the equation, the last term of the sum is zero (because when $i = k$, $k-i = 0$). So, the range of the first summation can be written as $1 \le i \le k-1$. Now, substitute $i$ with $k-i$. $i$ iterates over the set ${1, 2, ... , k-1}$ and $k-i$ iterates over the set ${k-1, ... 2, 1}$, ...


2

$1.6180^n$ is not an upper bound to the running time of your program, not even up to multiplicative constants (in fact it is a lower bound). However $O(\phi^n)$ is a valid upper bound, where $\phi = \frac{1+\sqrt{5}}{2} > 1.618$ is the golden ratio. It is also easy to see that your program takes $\Omega(\phi^n)$ time, so the above upper bound is ...


2

I know, that answer is done, is correct and is accepted, but let me add, that "function is bounded by $O(n^2)$" is not completely correct sentence and as such can lead to errors: $O(n^2)$ is set, so we can speak about boundedness by some member from it, but exact is to say, that function is bounded by some $\boldsymbol n^{ \boldsymbol 2}$ factor, ...


2

We have $n^2 + n = O(n^2)$. Indeed, if $n \geq 1$ then $n^2 \geq n$ and so $$ n^2 + n \leq 2n^2. $$


1

By showing a worst-case example, it doesn't show $O(mn)$ ... big-O is an upper bound, so when asserting a big-O runtime, it says that that algorithm takes $O(mn)$ time or better (remember that an $O(n)$ algorithm is also an $O(n^2)$ algorithm). But showing that there is an example that actually requires $kmn$ time means that the big-O runtime of $O(mn)$ ...


1

Judging from your description and your code, you are basically doing a merge of the two array but stop at the median. This means that your main loop (body) is executed $(m + n) / 2 \in O(m + n)$ times, which is linear in $m + n$. You could also figure that one out experimentally by trying your algorithm on a range of different inputs and plotting the time ...


1

What's wrong with (i) + j + k ? I live in a world where floating-point arithmetic has rounding errors, and where integer arithmetic has overflow checks, so (i + j) + k and i + (j + k) are most definitely not the same, for example if i is a large positive integer, and j, k are two large negative integers then the second one can produce an overflow (crash) ...


1

Yes, and you can even use the Floyd–Warshall algorithm as a black box, together with a post-processing step to achieve this. First, compute the shortest path between every pair of vertices using the Floyd–Warshall algorithm. Then, for each pair of vertices u and v and every special vertex w, compute the sum of the two shortest paths, the one from u to w and ...


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