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.
223 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
240
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
133
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
320
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
178
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
-4
votes
1
answer
112
views
What is the big O of this algorithm? [duplicate]
I think it's O(m*n) but someone said it's O(n). If you think it's O(n) could you provide an explanation?
def convert(self, s: str, numRows: int) -> str:
if numRows == 1:
return ...
- 103
0
votes
1
answer
118
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
363
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
672
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
249
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,165
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
541
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 ...
- 38k