New answers tagged

2

Let $c$ be the constant from part 2, and assume for simplicity that $n$ is divisible by $c$ (otherwise, query the first $n \bmod c$ bits). Partition the string into intervals of length $c$, and go over them one by one in an arbitrary order. The order doesn't need to be random – you can go over them from left to right. For each interval $I$, choose a pair $(i,...


0

I cant think of one simply way to solve such questions, but I can show you a way to start tackling the questions and making them simpler. In such cases, that $f$ recursively calls itself with their own return value, the running time of $f$ might depend heavily on its output. So contrary to usual complexity computation tricks, here we want to know precisely ...


0

Case 3 does not apply. Indeed: $$ f(n) = n \log n \not\in \Omega(n^{\log_9 10}) = \Omega(n^{\log_b a}). $$ However case $1$ applies since, for $0<c \le 0.01$ $$ f(n) = n \log n \in O(n^{1.04 - 0.01}) \subset O(n^{\log_9 10 - 0.01} ) \subseteq O(n^{\log_b a - c} ). $$ This shows that $T(n) \in \Theta(n^{\log_9 10})$.


1

The big-O notation (and also similar notations, such as big-Omega) are not inherently limited only to describe running time of algorithms. Indeed, when the context is the running time of some algorithm, there are no negative functions since algorithms cannot run "negative time". That being said, the big-O notation is a general mathematical ...


1

Python arrays have 0-based indexing, like in C, and unlike Fortran, which uses 1-based indexing. You can check Wikipedia for information about other languages. A python array $A$ of length $n$ consists of the elements $A[0],\ldots,A[n-1]$. The python function range(n) goes over the indices $0,\ldots,n-1$, and your range(1,n) goes over the indices $1,\ldots,n-...


0

The number of multiplications in the algorithm is $2n - 1$, but the number of multiplications in the Horner's method is $n$, which means this algorithm is not optimal. As mentioned in the Wiki page, Horner's method in evaluating a polynomial is optimal, therefore we can change this algorithm so that it uses the Horner's method. p = a[n] for i = n-1 to 0: ...


0

Worse-case complexity gives an upper bound on the complexity of an algorithm in terms of some parameters. Often the parameter is the length of the input, either in bits or in words, but sometimes several parameters are pertinent. The standard example is graph algorithms, where complexity is often expressed in terms of both the number of vertices and the ...


0

If we analyze a Time Complexity dependent also on the values of a given input, then as you say a more defined notation would be O(max(n)). Though, saying O(max(n) + n) in O notation means O(max(n)) So it will still be accurate, since in both outcomes the Complexity is linear in the given input.


0

Suppose that you start with some value in $x$. The inner loop increases $x$ by $i$. Therefore the outer loop increases $x$ by $1+2+3+\cdots+n = n(n+1)/2$. So overall, your code increases the value in $x$ by $n(n+1)/2$. The running time of your code is proportional to the number of times that $x$ is increased, hence it is $\Theta(n^2)$.


1

In answer to both of your questions:   Firstly, note that during the maintenance phase of the loop invariant proof, we are in the process of inserting u into S, and the way that y is defined is that it is a node in V\S while this is happening, therefore u and y exist in V\S at the same time when u is inserted. This answers your first question.   Secondly, ...


3

Let $I$ be your instance and consider the instance $I'$ obtained by replacing each bit vector $y$ in $L_1$ with $y' = y \oplus S$ (where $\oplus$ denotes bitwise xor). Call $L'_1$ the list containing all vectors $y'$. Consider the tuples $(x_1, x_2, \dots, x_l)$ and $(x'_1, x_2, \dots, x_l)$ where $x_i \in L_i$ and $x'_1 \in L'_1$. We have: $$ x_1 \...


0

There's no need to do any calculation. There is absolutely nothing special about the numbers 25 and 75. If $0 < \alpha < \beta < 1$ and you are promised that the median is between the $\alpha$'th percentile and the $\beta$'th percentile, then the running time of the algorithm will be linear. Indeed, if $\gamma = \min(\alpha,1-\beta)$, the length ...


0

There is an unwritten assumption that the input is always at least $1$ (otherwise your function never terminates). Under this assumption, it is easy to prove by induction that the function does terminate, and always returns $1$. Therefore in the expression $P(P(n/2))$, we are first invoking $P$ with the input $n/2$, and then with the input $1$. It follows ...


0

Let me add way with simple inequalities: $$n^2+n^3 \leqslant n^4 +n^4=2n^4 \leqslant 2(n^4+n) $$ Now taking constant $C=2$ we have $n^2+n^3 \in O(n^4+n)= O(n^4)$.


0

As Yuval has mentioned in the comment that the proof is based on the complete induction. However, an important thing is missing in the screenshot that you have shared. The "base case" is missing. Without the base case, the induction hypothesis and proof make no sense. Here, the base case is when $n = 1$. You might want to verify that $T[1] = O(1)$. ...


Top 50 recent answers are included