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.
222 questions
4
votes
4
answers
2k
views
Does the signature of a method create a dependency between the implementation of that method, and the code that invokes it?
I am reading Ousterhout's A Philosophy of Software Design. In Section 2.3, Outserhout writes:
The signature of a method creates a dependency between the implementation of that method and the code ...
- 49
0
votes
1
answer
278
views
How to deal with very complex codebase? [duplicate]
I recently changed my job to a big MNC and the code I am exposed to is highly complicated, difficult to read and understand. Although it is divided in microservices and runs on local I have to keep ...
- 11
1
vote
0
answers
146
views
Ideal Profits in companies in Perfect Binary Search tree
I'm trying to solve the following problems here:
In the X world, companies have a hierarchical structure to form a large binary tree network (can be assumed to be a perfect binary tree). Thus every ...
- 111
2
votes
3
answers
329
views
Does looping through n items always result in O(n) time complexity?
Summary
I saw a solution to a problem described as having O(c) Time complexity where c is the number of unique items in n.
I don't understand why we can say the complexity is O(c) despite looping ...
- 131
-3
votes
3
answers
212
views
NP-complete problem (subset sum) featured in Netflix series "Suits" S1 E8? [closed]
In the Netflix series Suits, Season 1, Episode 8 (Identity Crisis), the legal team, with the help of a hacker, is tasked with proving that a business magnate embezzled funds, splitting them and ...
- 203
0
votes
1
answer
133
views
Divide et Impera and P vs NP
Disclaimer: this is not an attempt at solving P vs NP, but a way for me to better understand the problem.
Let ¥(n) be the Subset sum problem, n being the number of inputs.
Trivially, a brute force ...
- 103
0
votes
0
answers
96
views
O(nlogn) + O(logn) =? [duplicate]
So I came upon this time complexity result and I was confused about it, it said that :
O(nlogn) + O(logn) =O(log(n+1))
Why is that the case? Shouldn't the result be O(nlogn)?
- 27
0
votes
2
answers
395
views
fastest way to find number of smaller elements to the right of an array
In Daily Coding Problem, Miller&Wu have the following problem :
Given an array of integers, return a new array where each element in the new array is number of smaller elements to the right of ...
- 181
0
votes
3
answers
727
views
Reducing Cognitive Complexity of Single-Responsibility "Arrow-Code"
Prompted by Sonar, I am looking to reduce the complexity of a function (one that some might call arrow code). I am loosely familiar with some of the principles of reducing arrow code complexity (...
- 111
-1
votes
1
answer
269
views
A data structure / algorithm to combine search tree and hash table?
I have a two dimensional data with one dimension is ordered and another one is categorical, for example, country and city_age:
country
age
city
Italy
2773
Rome
Germany
784
Berlin
USA
397
New York
...
- 157
14
votes
3
answers
5k
views
What are the complexities of a binary search?
I recently asked a question on CodeReview SE where using a binary search was recommended, and the author of the answer proved that it was faster than my implementation. During my research on the topic,...
- 1,175
4
votes
1
answer
1k
views
What is the most suitable data structure for IPv4 addresses with intersecting ranges?
Mostly in all routers and operating systems the Longest Prefix Match algorithm is used for searching the trie of IPv4 addresses.
Packet filters like Iptables don't need some special data structure for ...
- 99
0
votes
2
answers
1k
views
Calculating time complexity of a code snippet
I am trying to calculate the time complexity of the below code snippet
def func()
{
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j=j+i)
{
print("hello")
}
}...
- 111
3
votes
0
answers
570
views
Implementation of projections in event-sourced system
I'm working on a application which uses event-sourcing and CQRS to define it's domain model.
Background
We have implemented projections to aggregate stream of all domain events into a read models used ...
- 38.2k
4
votes
5
answers
419
views
Using dedicated functions for opposites/inverse
I have a disagreement with one of my colleagues on whether or not functions should have inverse functions available.
I would like to know when/if inverse functions should be used.
For example, say we ...
- 346
5
votes
2
answers
2k
views
Finding closest point in N dimensions in reasonable time (O(log(n) ?)
Is it possible to find the closest point (or k closest points) to any arbitrary point in a set of n points (in dimension N)?
When I write closest point, I mean smallest Euclidean distance. I'm looking ...
- 159
0
votes
2
answers
114
views
Small confusion about time complexity
Suppose we have a code:
for(int i=0;i<n;i++) sum+=i;
We say the time function here is: f(n) = n+1+n = 2n+1. The order of the time function is 1. So, our time complexity becomes O(n).
But, for the ...
0
votes
2
answers
124
views
Efficiency of different Processors and GPUs
My question is, knowing everything there is to know about several systems(CPU and GPU stats, OS), is it possible to approximate when each system will finish a specific processing operation?
And if it ...
- 131
0
votes
2
answers
198
views
Big O notation of a program that takes 10x time for 3n input
I have a program that calculates N digits of Pi.
I have measured that it takes 10x time to calculate 3n numbers, compared with the time for calculating n numbers. The source code also gives an ...
- 127
0
votes
1
answer
204
views
How should I apply dynamic programming on the following problem
I have an array of events where events[i] = [startDay_i, endDay_i, value_i]. The ith event starts at startDay_i and ends at endDay_i, Attending the ith event, I will receive value_i. Also given an ...
- 23
-2
votes
1
answer
116
views
What is the time complexity of this algorithm
This code is from https://www.geeksforgeeks.org/segregate-even-and-odd-numbers/
It takes an array of numbers & segregates them in place without bothering about the order.
void segregateEvenOdd(int ...
- 429
5
votes
4
answers
684
views
Processing a 2D matrix - need to speed up my O(n^4) algorithm
I have an n x n matrix which I need to convert into a list sorted by value. Starting with the maximum value cell at (row x1, col y1), I must immediately exclude all cells where (x >= x1, y <= y1)...
- 187
3
votes
3
answers
1k
views
Why am I getting complex errors even with simple C++ code?
I started to play with C++ recently. One of the difficulties I have quite often is when the compiler tells that there is an issue with the types: more often than not, those compiler errors look ...
- 139k
3
votes
1
answer
223
views
Nested loop complexity
I am working through MIT 6.006 OpenCourseWare as taught in Fall 2011. Problem 1.2c asks for the time complexity of an algorithm1 which finds a peak element (i.e. all neighbors are less than or equal) ...
- 141
21
votes
6
answers
5k
views
Using a different algorithm depending on the size of the input
I recently finished a course on advanced algorithms, and another on complexity & computability theory, and in the past few days my mind has been somewhat preoccupied by this question.
Why don't we ...
- 345
2
votes
2
answers
257
views
Time complexity for a small code
I'm trying to find the time complexity for the following code.
N= number of elements in array
D= a constant: D>1
V= a constant: V>1000
counter=1; //the maximum value of the counter is N/D.
...
- 37
-4
votes
1
answer
429
views
What is the worst case Time Complexity for only the Divide Portion of the Merge Sort Algorithm?
Please, consider the below merge sort algorithm. Here we start with a divide portion which splits the array into halves and we do recursive operation on each half separately. I have ignored the merge ...
- 1
-2
votes
1
answer
113
views
Is there a battery complexity similar to how there is time complexity and space complexity?
Understood that for all these ways of measuring the time and space is dependant on the users hardware, I was wondering is there is a similar way to calculate the battery usage of a program over n ...
- 99
0
votes
0
answers
82
views
Practical Understanding of Log a / Log b Running Time
Was wondering if someone could give a practical understanding of what it means for an algorithm to perform in (log a / log b) time?
In other words, practically speaking for an algorithm to perform in ...
- 1
0
votes
1
answer
257
views
Time complexity of an algorithm whose output does not scale linearly with the size of the input
Suppose I have a function CalculateOutput(n) which creates an array of size n and repeatedly modifies this array by iterating through every element from 0 to n - 1 (say this is done in linear time). ...
- 19
4
votes
4
answers
2k
views
Ahead-of-time compilation to native machine code of dynamically typed languages
It is my understanding that:
It's particularly difficult to compile ahead of time, to efficient native machine code, a dynamically typed language like Python.
Largely as a result of the above, the ...
2
votes
1
answer
123
views
Quantity allocation algorithm performance
I have a scenario for which I'll take an analogous example to help understand better.
There are N buckets of known varying capacities.
We have M balls that we need to put in these buckets to fill ...
- 129
14
votes
2
answers
5k
views
Time Complexity of Parallel.ForEach
Pseudo code and comments to explain:
// first select companies to process from db
foreach (company) {
// select the employees
foreach (employee of company) {
// select items they can ...
- 251
2
votes
0
answers
129
views
Code quality balancing with need to perform scientific analysis on your own software
We have a project that is meant to do signal processing. If all we had to do with the software was that one job, we would have a pretty clean architecture. Unfortunately, we've run into an issue most ...
- 1,347
-2
votes
1
answer
377
views
Why does Halstead's formula for estimated program length look like this?
According to the Halstead's software metrics:
Estimated program length:
Can you please explain me, why the formula uses logarithm to base 2? Why not something else? Why exactly logarithm? What’s ...
- 117
4
votes
2
answers
2k
views
Summing cyclomatic complexity of function or files
Is the sum of the cyclomatic complexity of all section in a file the total cyclomatic complexity for this file? If it is, is the sum of a set of related files the total cyclomatic complexity for this ...
- 83
-1
votes
1
answer
147
views
time complexity for 3 foor loops different leangth [duplicate]
I have this method
arr // input
new_ seq = []
for i in arr:
new_seq.append(i)
__new_seq = [x for i, x in enumerate(arr) if x not in new_seq]
for j in __new_seq:
new_seq.append(j)
...
- 13
4
votes
1
answer
338
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,...
- 151
1
vote
3
answers
239
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(...
- 2,128
0
votes
1
answer
630
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 ...
- 101
1
vote
1
answer
488
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 ...
- 113
2
votes
2
answers
4k
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:
...
- 33
5
votes
2
answers
2k
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 ...
- 572
1
vote
2
answers
716
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 ...
- 133
-2
votes
1
answer
156
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")
....
- 10.2k
0
votes
3
answers
107
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;
...
- 169
12
votes
3
answers
878
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 ...
- 569
0
votes
1
answer
48
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). ...
- 345
0
votes
2
answers
2k
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. ...
- 232
-2
votes
1
answer
39
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 ...
