Hot answers tagged

25

That depends what exactly you mean by "constant sized". The time to find the minimum of a list with 917,340 elements is $O(1)$ with a very large constant factor. The time to find the minimum of various lists of different constant sizes is $O(n)$ and likely $\Theta(n)$ where $n$ is the size of each list. Finding the minimum of a list of 917,340 ...


13

I found this quote from the Wikipedia article on time complexity helpful: The time complexity is generally expressed as a function of the size of the input. So if the size of the input doesn't vary, for example if every list is of 256 integers, the time complexity will also not vary and the time complexity is therefore O(1). This would be true of any ...


6

I can't answer that question reliably, because it depends on the behavior of the memory allocator in Python, and I don't think we're provided any guarantees about that. The memory allocator might deallocate the space after the function returns, or it might deallocate in every iteration. What we can say is that it is possible to implement this algorithm ...


5

Sure, you could call it O(1) if you want. So what if you choose to describe it that way? It's still going to iterate over the whole list, so describing it one way or the other doesn't change the real-world Python run time. It's still something you want to avoid doing repeatedly for the same list, especially if the list isn't tiny. (Especially in a loop ...


4

Yes In general, if the time complexity of an algorithm is O(f(X)) where X is a characteristic of the input (such as list size), then if that characteristic is bounded by a constant C, the time complexity will be O(f(C)) = O(1). This is especially useful with certain algorithms that have time complexities that look like e.g. O(N ^ K). This is superexponential,...


4

The python creators decided that any expression is valid as a statement. While not all expressions are useful as statements, it would make the language more complex to have to remember which expressions may be statements and which can not. A second reason is that many expressions that may seem "safe" can still have side effects, making it useful to ...


4

For odd-sized boards, a knight's tour must start and end on the same color as the corner squares of the board. It follows that for about half (50%) of starting squares, there is no possible knight's tour and the search is bound to fail, explaining your error rate. In contrast, for an even-sized board, the knight can start on either color. I didn't read your ...


3

In the copy that I have of IEEE 754 (2008) it says 7.3 Division by zero 7.3.0 The divideByZero exception shall be signaled if and only if an exact infinite result is defined for an operation on finite operands. The default result of divideByZero shall be an ∞ correctly signed according to the operation: ― For division, when the divisor is zero and the ...


3

The Bentley-Ottmann algorithm can be used to find all intersections between edges, and then you can add a node at each such intersection.


3

The running time is polynomial with memoization. If the original input string has $n$ characters, then there are only $O(n)$ possible suffixes of the original string, the function is only called on a suffix of the original string, and (ignoring recursive calls) the time to execute the function is polynomial; so the total running time with memoization is ...


2

Assuming that sorted() really takes time $O(n)$, then the time and space complexities are indeed $O(n)$. Hoewever there are some catches. You say that the zip function takes $O(1)$ time. This is technically true, but you should be aware that zip is not creating a list that contains pairs of elements from a and b but just returning an iterator to these pairs. ...


2

If the size of the lists as input to the min() and max() functions always are the same constant $k$, then you can find an upper bound (and lower bound) on the number of operations required to compute min() and max() that depends only on the constant size $k$ (plus some other constants), which results in a running time of $O(1)$. Therefore, if the size of the ...


2

Colloquially we refer to algorithms as $O(1)$ or $O(n\ \log n)$ or such. When you start talking about the Big-O complexity class of an operation over a constant sized object, it becomes important to use it more precisely. Us CS people get too lazy! Big-O notation is applied to mathematical functions not computer algorithms. It explores the bounds on an ...


2

Yes, any bounded amount of work is O(1). Every algorithm applied to an input of bounded size takes O(1) time, however, and that is independent of any variables whatsoever, so there is never any reason to mention this as an attribute of any particular algorithm. In the analysis of algorithms, though, you will often see O(1) used to refer to any bounded amount ...


2

Usually, $\operatorname{O}\left(1\right) .$ Yeah, usually it'll be $\operatorname{O}\left(1\right) ,$ under normal assumptions. A major exception would be if the list-elements could grow in complexity with input-size. For example, if the list-elements were themselves lists that grew with the input, then even a single comparison between two of the elements ...


2

Notice that the loop will only occur once! In the beginning num will be 0. At this point, we enter the if statement: if we got that str[0] == ch (notice that num==0 and thus str[0]==str[num]), then we return some string otherwise we return another string The important thing here, is that no matter what - we will quit in the first iteration of the for loop. ...


2

As Emil said, That is the number of milliseconds since the Unix epoch (1 Jan 1970 midnight UTC).


2

Matlab gives infinity because it's working directly with floats. IEEE754 floats attempt to let errors propagate through a computation instead of immediately crashing a program when something such as division by zero is encountered. Python division, whether integer or float (1/0, 1.0/0.0, 1//0), all have special checks for integer division at the software ...


2

Indeed: Python supports OOP, but unlike Java, doesn't enforce it. So that seems the most accurate statement regarding the matter. Based on this, it makes sense to say that Python is OOP but less so than Java, or Python is not OOP but supports it; but why would you? These statements are vague. They invite confusion. Why not just say what you mean instead of ...


1

The compilation process is a process of taking code from language "A" and translating it to code from language "B". Lets start by saying that python doesn't compile at all - it stays python code all of the time. On the other hand, $C$ compiles into assembly, which then turns into a standalone executable. Since python stays python, this ...


1

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) # ...


1

This one seems to be working well for me. Try out without the swap function.


1

Given a positive integer $x$ let $n_x = \lfloor \log_{10} x \rfloor$ and let $x_0, x_1, \dots, x_{n_x} \in \{0, 1, 2, 3, 4, 5, 6, 7 ,8 ,9\}$ such that $x = \sum_{i=0}^{n_x} 10^i x_i$. Define the multiset $S(x) = \{x_0, x_1, \dots, x_{n_x} \}$. The problem is asking for: $$ \min x \quad\mbox{ s.t.}\\ S(x)=S(ix) \quad \forall i \in \{2,3,4,5,6\}; \\ x \in \...


1

The first step is to observe that the relationship can be achieved by multiplication of signs. With numpy.sign(x) we get 0 if x is zero, 1 if positive and -1 if negative, since you check for sign equality, multiplication by the same sign value will always be 1, multiplication by 0 always yields 0 and multiplication by opposite signs yields -1. import numpy ...


1

Python can be used interactively, in which case the bare expression's value (if any, it might be None) is printed out. If running a script or as part of a function, the value is just discarded. If you look closely, Python only has functions (no procedures in e.g. Pascal sense or SUBROUTINE for Fortran that specifically don't return a value at all). Like in C,...


1

The following two points might clear your confusion. The pseudocode in the book is following $1$ based indexing. Your code is following $0$ based indexing. Your code is technically doing nothing in the first iteration of the while loop. In the first iteration $i = 0$, therefore $j = -1$. Since $j<0$, the inside while loop is not executed. And it keeps $...


1

It depends on the definition of in-place algorithm you are using. if in-place just means that the algorithm transforms the input without returning a new array, then yes; if you also want to use no additionnal data structure, or limit the additionnal space usage to be $o(n)$, then no, because of the creation of the arrays count and output. There are ...


1

The data you have is just a large integer. So you parse it like you would parse any large integer. Now there should be documentation what the integer means - if there is none then you will guess. If the number was days since a date X, calculate what X would be. If the number was seconds since a date X, calculate what X would be. If the number was nanoseconds ...


1

Lets deal with the issues one at a time, since there are a few of them. Problem 1 Take a look at those lines of code: trow = [0] * (m+1) table = [trow] * (n+1) srow = [""] * (m+1) solution = [srow] * (n+1) The problem with this code, is that the same list is being placed a few times. This means, that every list in $table$ must be all ...


1

Programming questions are off-topic here. Anyway your matrices table and solution are not properly initialized as they contain references to the same objects. Try: table = [[0]*(m+1) for j in range(n+1)] solution = [ ["" for i in range(m+1)] for j in range(n+1) ] Moreover, the returned string should be solution[n][m] and not solution[n-1][...


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