# Tag Info

## New answers tagged complexity

-3

#Matrix rotation def rotateMatrix(a): b = [] d = [] for i in range(len(a)): for j in range(len(a[i])): b.append(a[j][i]) if len(b) == len(a): d.append(b[::-1]) b = [] return d a =[[1,2,3], [4,5,6], [7,8,9]] r = 360 def matrixRotation(a,x): if r == 90: print(...

7

The algorithm provided by the OP presumes that the array is important and preserves the original array. In addition, the displayed algorithm seeks an "instantaneous answer", as if the routine may be interrogated at any point to get that answer at the point in time. All that is important here is the output - a single number. Any other information used to ...

5

Better complexity can be achieved using a heap. The input array can be organized into a min-heap in $O(n)$ time with negative integers dropped. Then the smallest number can be popped one by one until the target number is found. The complexity of this algorithm is $O(n + klogn)$ where $k$ is the insertion index of the target number among the sorted ...

8

I then tried putting the array into an arraylist, which reduces big-O since each object is "touched" only once, and I can use .Contains which is more efficient than iteration (not sure if that's true; I just sort of remember reading it somewhere). As was mentioned in the comments, for your purpose, there is no significant difference in performance between ...

1

Maybe the code is time efficient because you are lucky. Maybe the code is time efficient because you have good intuitions. This review is about moving toward luck playing less of a role in the performance of your code and/or reaching good intuitive conclusions by a more formal path. Top Down The code seems to be written bottom up from loops rather than top ...

0

Not sure how using roots help you, but here is my solution to the porblem (a pyramid, n-th row has length of n): EDIT: I assumed that if the number won't be a perfect pyramid (like 24) then print until the number. If you want to print the biggest pyramid possible it simplifies the code a bit. public static String pyr(int n) { //n is the target num ...

1

As @BlindMan67 commented, the Nodes themselves are not protected. Apart from that, I don't see many glaring problems. Below is a short example of how to fix that (However, it does use a function closure, which may not be your style) const [Deck, Node] = (function() { // Class definition for nodes, not included const NodeHeads = new Map(), ...

2

You're doing things quite the hard way. You don't need to call sqrt, or determine perfect squares at all. Simply track y, and as soon as the row's x == y, make a newline, increment y and set x = 0. The following examples show different results from what you've described: import java.io.StringWriter; import java.lang.Math; class Pyramid { interface ...

2

The linearity of your approach is due to the fact that your longest could never be longer than the size of the alphabet (otherwise it'd have a duplicate for sure). It means that your code runs at $O(N * A)$, where $N$ is a length of the string, and $A$ is a size of alphabet. Since the latter is a constant, you may safely take it out of the big-O, ...

3

""" Module Docstring This is a simple object-oriented implementation of merging two Single Linked Lists with some associated methods, such as bubble sorting, create list, and such. """ The line Module Docstring is probably a placeholder which you're meant to remove, but it's good to see that the methods are documented. def create_list(self): ...

2

Docstrings You should have a docstring at the beginning of every module, class, and method you write. This will allow documentation to identify what your code is supposed to do. You're on the right track, having comments above the classes and methods. Now, just move those comments inside these classes and methods at the very beginning, inside triple quote ...

2

This is your bottleneck in retrieving the new head at removal, which can not be avoided in a Singly-Linked structure, so it's $O(n)$. while (temp.Next != head) // Get the previous Node of the head temp = temp.Next; Doubly-Linked If you want fast removal $O(1)$, you can do so at the cost of slightly slower insertion. You'd need to augment the ...

2

... for digit in num_as_string[::-1]:. In this loop, it's just $O(n)$ where n is just number of digits of the input. I am assuming the time complexity of this code is something like O(n) + 2 * O(number of digits in base10) which is linear. This is not quite right. The second and third loops will loop the number of digits in base $b_2$ (not in base ...

2

Much of the following feedback is not really performance-related, but will make the code more easily legible and easily analyzed for the purposes of performance improvement. Add type hints b1 and b2 are presumably int, so add : int after their declaration. num_as_string and the function's return value are both str. Multiple assignment ...has its limited ...

3

General Review Make all instance fields that are never reassigned final. From the comments you suggest some of these fields get reassigned later in the code. In this case, those fields should not be declared final. private final PriorityNode<T>[] items; private final Set<T> itemSet; Make constants static and readonly, and use underscores for ...

2

There is a much easier solution which is strictly $\Theta(n)$. Given $\ell$ the input list: Filter for just positive numbers: $\ell_{>0} = \{i \in \ell\mid i > 0\}$ Compute the maximum and the sum of the elements of $\ell_{>0}$. Namely, $m = \max \ell_{>0}$ and $s = \sum _ {i \in \ell_{>0}} i$ Now there are two cases: whether it ...

2

Performance and readability are often a trade off. This $O( n \log n)$ solution just misses the $O(n)$ target, because we must sort the pre-filtered array, but it’s much easier to reason about a map/reduce in my opinion. Integer[] nums = {1,2,0}; //Integer[] nums = {3,4,-1,1}; //Integer[] nums = {1,2,4}; //Integer[] nums = {1}; //Integer[] nums = {0}; ...

Top 50 recent answers are included