Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

-2
votes
0answers
30 views

Run time of Algorithm with nested loop

(a1,...,an)(b1,...,bm) x <- 0 i <- 1 while i < n and ai > 0 do for j <- i to m do x <- x + ai x bj i <- i + 1 return x So with this algorithm I've been ...
1
vote
1answer
46 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 ...
2
votes
2answers
110 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: ...
4
votes
2answers
213 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 ...
0
votes
1answer
123 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 ...
0
votes
0answers
32 views

Combine n-Linear Series into DataGrid

I'm scratching my head at this, I really need to redesign the schema of an old existing data concept we have in our db. The more I work on it, the more I see why they took an easy way out. Currently, ...
-2
votes
1answer
71 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") ....
0
votes
3answers
78 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; ...
11
votes
3answers
306 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 ...
0
votes
1answer
32 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). ...
0
votes
2answers
218 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....
-2
votes
1answer
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 ...
1
vote
1answer
131 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)...
19
votes
6answers
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 ...
1
vote
1answer
101 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 ...
2
votes
2answers
138 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 ...
0
votes
1answer
41 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 ...
0
votes
0answers
145 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 ...
0
votes
3answers
142 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 ...
2
votes
3answers
224 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 ...
-1
votes
2answers
111 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}...
0
votes
3answers
347 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 ...
0
votes
1answer
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)...
1
vote
4answers
504 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? ...
1
vote
1answer
100 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 ...
1
vote
1answer
120 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 ...
2
votes
2answers
411 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] == ...
-4
votes
1answer
87 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 ...
6
votes
3answers
307 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 ...
6
votes
3answers
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 ...
18
votes
3answers
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 ...
3
votes
2answers
208 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 ...
3
votes
1answer
216 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 "...
1
vote
0answers
130 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 ...
3
votes
1answer
430 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 ...
1
vote
2answers
136 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 ...
1
vote
2answers
164 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.
1
vote
3answers
366 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 ? ...
1
vote
4answers
954 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 ...
2
votes
7answers
622 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 ...
-1
votes
3answers
145 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;
-3
votes
3answers
558 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 ...
1
vote
1answer
235 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, ...
-1
votes
1answer
48 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]; } ...
2
votes
2answers
119 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 ...
2
votes
1answer
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 ...
0
votes
1answer
128 views

Trying to find time complexity of modulus algorithm

I can't quite figure out the time complexity of this algorithm I've written for finding the modulo. I've added it here in psuedocode. Modulo(int x, int n) // x is the dividend, n is the divisor e ...
0
votes
1answer
402 views

How to calculate big O notation according to number width?

I'm trying to understand big O with the bitwise operations. I have 2 functions those are solving the same question from different perspective. num1BitsSecondSolution starts to shift the number right ...
1
vote
1answer
178 views

Complexity of recursive calls

my brain is a little stuck as I am trying to compile an example for my blog. I am presenting an algorithm that draws a number from an array, adds it to a sum and calls itself recursively. func solve(...
1
vote
2answers
75 views

Modulo complexity within nested loop

i have following code: for ( int i = 1; i < n; i ++) for ( int j = 0; j < n*n; j ++) if (j % i == 0) for (int k = 0; k < j; k++) sum++; How would if (...