Make your voice heard. Take the 2019 Developer Survey now

# Questions tagged [complexity]

Complexity deals with various forms of calculating the complexity of code. Cyclomatic complexity, n-path complexity, Big O time and space complexity.

187 questions
4 views

### time complexity for 3 foor loops different leangth

I have this method arr // input new_ sequence = [] for i in arr: new_sequence.append(i) for j in arr if j not in new_sequence: new_sequence.append(j) for k in arr if k not in ...
77 views

### How should I document a method's computational complexity in the code?

I am currently working on a project that has very little documentation overall. The team is working to change that. I am doing my part, by adding xml comments to the methods I make and the ones I edit,...
170 views

### Big O Complexity when iterating in 3 dimensions

What time complexity would you classify the following as having? int n = 100; for(int x = 0; x < n; x++) for(int y = 0; y < n; y++) for(int z = 0; z < n; z++) DoWork(...
21 views

### Question on complexity of Barnes-Hut algorithm

A common algorithm used in N-body gravitational calculations with large numbers of bodies (stars in a galaxy, galaxies in the universe, etc.) is the Barnes-Hut algorithm, which assembles particles ...
59 views

### How to identify additional space complexity

I just started leaning about algorithm design and I am now having trouble identifying the additional space used in an algorithm. For dynamic program, as far as the examples I've learnt, such as ...
169 views

### Can nested loop have linear time complexity

I was going through the traditional quick sort algorithm. I had a look on the partition algorithm in a couple of places and the implementation difference was very subtle. Here are the 2 approaches: ...
223 views

### How to keep track of growing catalog of business rules?

Building my last application, everbody started to lose control over the increasing complexity of business rules, which would be added every week - most of all the app owners themselves. In the end, we ...
131 views

### Execution time of an algorithm on faster computer?

An algorithm takes 1 second to execute a dataset of size N on a particular computer. Replace it with a computer that is 10 times faster. What will be the size of the dataset you can process in 1 ...
76 views

### How to measure complexity of expressions?

I'm comparing two APIs to generate a method in C# and want to measure how "complex" the code to use them is. Consider: API A: MethodDeclaration(PredefinedType(Token(IntKeyword)), "CompareTo") ....
79 views

### Abstract responsibility from caller without introducing complexity

I have two classes: public class Child { public List<Vector2> localPoints; public List<Vector2> localEdges; } public class Parent { public List<Child> children; ...
315 views

### How to measure the complexity in practice in your large software project?

In university, at our algorithms courses, we learn how to precisely compute the complexity of various simple algorithms that are used in practice, such as hash tables or quick sort. But now in a big ...
33 views

### Assembling random indexed packages into an ordered sequence(s)?

I am pretty confident that this is well-known and solved problem. Suppose there are n uniquely indexed "packages" randomly getting into single entry point like .AcceptPackage(Package package). ...
268 views

### What is meant with finding real and integer constants in Big Oh notation?

From my book "Data Structures & Algorithms in Java: Sixth Edition" the definition of Big Oh is the following: Let f(n) and g(n) be functions mapping positive integers to positive real numbers....
29 views

### Finding 3 equally spaced boolean cells

Given an array A[N] of N booleans, return a, b such that a >= 0, b > 0 and A[a] = true A[a+b] = true A[a+2b] = true or -1 if they don't exist. The best algorithm I could find was brute forcing ...
140 views

### Am I allowed to simplify terms while calculating Big O?

I want to calculate the runtime of the following function T(n) = (1+2+3+4+5+...+n)/n At first this doesnt seemed hard to me because it can be solved easily by transforming the formula T(n) = (n(n-1)...
4k views

### What do you call it when you change the Big O execution time of a function [closed]

Let's say I have a function which sorts a database in O(n^2) time. I want to go about refactoring it so it runs in O(n log(n)) time, and in doing so I will change the fundamental way the operation ...
103 views

### What does it mean “state complects value and time”?

I'm rewatching Rich Hickey great talk "Simple Made Easy" And around min 35:40 when talking about state, mentions that State complects value and time, but I'm not sure I'm understanding this well. Is ...
140 views

### how do you automate multiple reports requirements that are complex?

I was tasked to automate reports used by multiple teams. Each team have their own procedure on how to generate the report that they need to deliver. I can automate the reports but it takes so much ...
42 views

### Would it make sense to count cyclomatic complexity for design diagrams?

I know CC is counted at the code level to determine a set of basis paths (i.e. independent paths), the elements of which then can be combined to create any possible execution paths. In software ...
178 views

### Data structure to implement a fake filesystem with required complexity functions

I have to create a fake filesystem that basically stores the path of each element in the structure. This filesystem has to run on the primary memory so I do not have to write anything to the hard ...
143 views

### Big-O when worst case numerical value is known

If I have an algorithm and part of it has a known worst case numerical value, which is reasonably small compared to the rest of the problem, is it ok to argue that part as O(1)? E.g. If part of the ...
229 views

### Should I introduce tools even if I might not need them right now

I recently read two articles regarding two different approaches for managing the underlying technologies of a system. The first one was by engineers of reddit, explaining how they gradually extended ...
124 views

### Why in Tournament Sorting do we neglect the number of comparisons to find the Minimum?

Here the professor said that, Tournament sort needs (n-1) + 2(n-1)logn comparisons. {Where (n-1) for calculating Maximum or say creating Tournament structure and 2(n-1)logn for other elements to sort}...
419 views

### Code pattern to have the least possible code complexity (Javascript)

I've been looking for the ideal coding patterns used to score well in a Cyclomatic Complexity. Of course, code will be subject to change according to what is being developed but regardless the ...
2k views

### Comparing Two JSON Files In O(n)

I've got a scenario where I need to compare two JSON files and override one if the values are different. These JSONs also include arrays (i.e. [) My approach is to traverse one JSON to dictionary O(n)...
556 views

### How to prevent over-engineering from Developers? [closed]

What are some techniques that you can use to prevent over-engineering among the Software Developers? Meaning, how do you keep them focused on creating solutions of only the current requirements? ...
103 views

### Key indicators/determinants that an algorithm has a time complexity of factorial or exponential?

There seems to be significant amount of deep information on the lesser time complexities: linear, polynomial, logarithmic; But there isn't a good source of deep information on how to easily determine ...
123 views

### Performance: Looping on data on the server or getting data looped on clients via socket connection

I have a web application the mobile app users are connected it by using websocket. The server has data A that can be changed in time. And the clients (mobile app) have data B that also can be changed ...
421 views

### Is a procedure's complexity a function of how many nested loops it has?

Take this example public static boolean uniqueNumbers(int[] x){ for(int i = 0; i <x.length; i++){ for(int j = 0; j <x.length; j++){ if(i != j && x[i] == ...
89 views

### Calculating Complexity

I am having trouble calculating the complexity of this problem: REVERSE3(A): // Reverse the order of elements in an array // P is an array; assume generating next permutation takes 1 step. for ...
388 views

### How to cleanly implement permission based feature access

I have been tasked with writing an on/off control for features in our product based on who is signed in, in principle with one on/off flag for each feature. Put simply, this is a permission based ...
1k views

### Cyclomatic Complexity spread over non-reusable functions

I am frequently writing parser and mappers of some sort. This means that the switch statement gets used a lot and often many if statements for checking for valid input. This of course creates a lot ...
1k views

### Is there a term for over-complication of OOP?

A year or two ago I saw an excellent article on OOP (Java), which showed the progression of a simple concrete logger of two or three lines of code, and a theoretical excessive thought processes by the ...
226 views

### Arrays vs Dynamic Arrays

In Steven Skiena's The algorithm design manual Edition 2, he talks about dynamic arrays on page 67, which results in them having same Big-Oh as normal arrays. I don't understand how. This is what book ...
245 views

### Maintenance Complexity of Gradle build scripts

I am currently trying out Gradle for my embedded development project. The existing tool is GNU Make. Across the internet I have read a lot of articles where people say that their build logic becomes "...
131 views

### Algorithm to find region with least-probable density

Consider the following boolean array where dark == true: In this scenario the probability that a cell is dark or light is 50/50, but this may not be true for the general case. Maximizing only on ...
442 views

### Algorithms comparison and complexity

I want to sole this problem: Write a method to return all valid combinations of n-pairs of parentheses. The method should return an ArrayList of strings, in which each string represents a ...
138 views

### Evaluating the cost of a query in database

We are working on a project using Google App Engine + Google Cloud Datastore. The language used is Python. At some points of our API, we check if some arg is passed in request, and we make some query ...
166 views

### What is name of this type of complexity?

What is complexity related to number of operations/interactions between objects within a system? as that number increases the programmer capability of understanding and maintaining the system degrade.
385 views

### Find if any pair exists in an unsorted array?

I have come across a programming question in which I have to determine : Does there exists at least one pair in a given unsorted array such that |i - j| <= K and |A[i] - A[j]| <= x ? ...
1k views

### How does the dividing Step in Merge Sort have Constant Time Complexity?

I am highly confuse while calculating time complexity of Merge Sort Algorithm. Specifically on the Dividing Step. In the dividing step we have to calculate the mid point of "n" i.e. "q = n/2". How ...
667 views

### Do we really need efficient algorithms? [duplicate]

I'd like to ask why people devote their time to research algorithms and their efficiency so extensively when computers nowadays are so fast. Trying to come up with an answer I thought that maybe my ...
151 views

### Time complexity of an algorithm [closed]

What is the complexity of the following loop? for(i=1;i<n;i=2^i) sum+=i;
599 views

### inheritance and polymorphism decrease readability

Most of financial apps have complex calculations and over time have change in calculation methods. Then you mostly create a new version for your calculator class that extends previous calculator and ...
241 views

### Big-O notation and halting problems

I'm trying to understand why it's impossible to create a tool that calculates Big-O notation automatically. I have read about Halting problems, but not related on Big-O notation and I was wondering, ...
50 views

### Time complexity Computation

What will be the result of the time complexity of this piece of code i.e. int sum(int A[], int n) { int sum = 0, i; for(i = 0; i < n; i++) { sum = sum + A[i]; } ...
121 views

### how to program a lookup table of input and output variables

This is a small C++ application (and the table is not huge either) so if possible I would like to avoid include anything other than STL (and boost). So to the problem: I have a table of predefined ...
82 views

### How do I determine correctness of a codes complexity?

Given a piece of code, I may use one of many methods to determine the big O complexity of the code manually (runtime and memory). But, for a given piece of code, how do I determine whether what I ...