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
4votes
4answers
2kviews
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 ...
0votes
1answer
240views
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 ...
1vote
0answers
133views
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
2votes
3answers
320views
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
-3votes
3answers
178views
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
-4votes
1answer
112views
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
0votes
1answer
118views
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
0votes
0answers
96views
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
0votes
2answers
363views
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
0votes
3answers
672views
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
-1votes
1answer
248views
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
14votes
3answers
5kviews
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
4votes
1answer
1kviews
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
0votes
2answers
1kviews
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
3votes
0answers
541views
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
