Complexity deals with various forms of calculating the complexity of code. Cyclomatic complexity, n-path complexity, Big O time and space complexity.
1
vote
1answer
17 views
How an add vertex operation could be performed in constant time for a graph represented using adjacency list?
Adding a vertex in a graph that is represented using an adjacency list takes O(1) time complexity according to http://bigocheatsheet.com/ (graph operation > adjacency list > add vertex).
It is said ...
3
votes
1answer
60 views
why adding a vertex in a graph represented using an adjacency matrix takes O(|v|^2) time complexity?
Adding a vertex in a graph that is represented using an adjacency matrix takes O(|v|^2) time complexity according to http://bigocheatsheet.com/ (graph operation > adjacency matrix > add vertex).
But ...
7
votes
4answers
556 views
Reducing the complexity of a class
I have looked at some answers and searched on Google, but I could not find anything helpful (i.e., that wouldn't have awkward side effects).
My problem, in abstract, is that I have an object and need ...
5
votes
3answers
260 views
Is O(log n) + O(log n) = O(n)? [duplicate]
We know that binary search takes O(log n) in Big O notation but if we need to run twice an algorithm of O(log n), would it be the same as O(n) in time complexity?
For example, if I have a method to ...
-3
votes
0answers
18 views
What's the complexity of all unique pairs in a collection? [duplicate]
For example, what is the complexity of the following algorithm?
Body[] bodies = new Body[n];
for (int i = 0; i < bodies.Length; i++) {
for (int j = i + 1; j < bodies.Length; j++) {
...
2
votes
1answer
46 views
Time complexity of update and lookup in binary random access list
I'm trying to get through one of the exercises in Okasaki's "Purely Functional Data Structures," where he presents a zeroless binary numbers as a structure for random-access list, and asks to
9.6 ...
5
votes
3answers
152 views
Why don't “multi-infinite” list comprehensions work with lazy evaluation?
As a simple demonstration of the efficiency of Haskell style, I thoughtlessly ran the following:
take 100 [(a, b, c) | a <- [1..], b <- [1..], c <- [1..], a^2 + b^2 == c^2]
This should be a ...
-4
votes
3answers
359 views
How can the containsKey() method of a Java Hash Table be O(1)? [duplicate]
I had a very large ArrayList in Java, and I often need to check if it contains a particular value. This has proven very slow.
Then I discovered that you can use a data structure based on a Hash. ...
3
votes
1answer
117 views
What is the time complexity of this program?
An algorithm is given on GeeksForGeeks.com for constructing a Binary Search Tree from its preorder traversal.
They say that the time complexity for the following code is O(n^2). But in my opinion it ...
2
votes
1answer
74 views
Seeds distribution algorithm with complexity better than O(n^3)?
I have included my approach and solution. My solution works fine, however, is unoptimized with O(n^3) complexity
An NGO is running seed distribution program. It has limited quantity of varied quality ...
0
votes
2answers
187 views
Efficiently find whether Binary Search Tree is Height Balanced or not?
A binary tree is height balanced if and only if the two subtrees of root are height balanced and the difference between the two subtrees height is at most 1.
I implemented a code in java to find ...
15
votes
4answers
954 views
Are Constant Time and Amortized Constant Time effectively considered equivalent?
I need to write a RandomQueue that allows for appends and random removal in Constant Time ( O(1) ).
My first thought was to back it with some kind of Array (I chose an ArrayList), since arrays have ...
-3
votes
4answers
133 views
Time complexity of this loop [duplicate]
Is the time complexity for this loop O(n) or O(log n)?
for(i=0;i<n/2;i++){}
I am thinking, the time is proportional with the input size.
0
votes
1answer
135 views
What are the time and space complexities of this recursive method that reverses a singly linked list?
What are the Time and Space complexities of this Java method that reverses a singly linked list (of length n)?
I'm more interested in knowing the reasoning behind the space complexity. Let me know if ...
0
votes
1answer
65 views
Do Temporary tables have any form of index in SQL?
Consider a simple query like this:
SELECT * FROM DATA
JOIN
(
SELECT * FROM DATA
)TEMPORARY_DATA
ON TEMPORARY_DATA.DATA_IDN = DATA.DATA_IDN
What is the performance of this? Is it O(n2) because ...
2
votes
1answer
74 views
Find all factors(prime and composite) of a number
We can find all the prime factors using a Sieve of Erastothenes. But how do we find ALL the factors of a number?
For instance, 24 = 2x2x2x3
But the complete factor list is - 1,2,3,4,6,8,12,24.
I am ...
-3
votes
1answer
112 views
Big O notation for a sub linear algorithm [duplicate]
I have a function for which the complexity raise by the square ten of the exponent of the number.
Ex:
+-----+----------+
|Input|Complexity|
+-----+----------+
|0 | 1 |
|10 | 2 |
...
2
votes
2answers
201 views
Finding the first subarray that sums to a given total
Due to the failure of comprehension of the last version here is the question.
Given and unordered array of positive and negative integers. How can you find the first subarray to sum to a given ...
2
votes
3answers
123 views
Complexity analysis: Finding common members of unsorted arrays
I've been going over previous tech interviews I've had (got another one coming up).
The problem
Anyway, one question I had was...
Given 2 unsorted arrays how would you find all of the common ...
1
vote
0answers
68 views
A fast algorithm for a simple multi-objective minimization?
I have a set of n (arbitrary) integer numbers S which I want to partition into k subsets S_i each of size n/k (you can assume that k divides n). Let A be the arithmetic mean of elements of the set S. ...
1
vote
4answers
142 views
What do polynomial algorithms entail?
From here, I know it is that an algorithm that...
...is said to be solvable in polynomial time if the number of steps required to complete the algorithm for a given input is O(n^k) for some ...
1
vote
1answer
217 views
Why does this algorithm work in O(n m)?
This is from a blog post on Codeforces. I couldn't really understand why the editorialist goes on to claim that this code works in O(n m)
This is a graph problem, where we are supposed to find the ...
2
votes
1answer
78 views
If I replace N objects with N pointers, is my space complexity still O(N)?
Lets say I get N objects as input, and I need to rearrange them into a different data structure. This means the space complexity of my algorithm will be O(N). But what if I replace the objects with ...
57
votes
6answers
6k views
Why aren't there code overviews for open-source projects? [closed]
There are very complex open source projects out there, and to some of them I think I could make some contributions, and I wish I could, but the barrier to entry is too high for a single reason: for ...
0
votes
1answer
140 views
What is the justification for the running time of this loop?
I don't understand why the running time of the following loop is n+2 ? Also why the running time of the statements inside the loop is n+1 ?
Double test(int n){
int sum=0; -> 1 time
...
1
vote
3answers
151 views
What is the rule for simplicity over complexity? [closed]
We have a site which is hugely complex in its implementation. Conceptually, it is simple - a web-based catalog. But the implementation has become a multi-layered nightmare.
Can anyone indicate a ...
16
votes
16answers
2k views
Do else blocks increase code complexity? [closed]
Here is a very simplified example. This isn't necessarily a language-specific question, and I ask that you ignore the many other ways the function can be written, and changes that can be made to it.. ...
188
votes
16answers
31k views
What's wrong with comments that explain complex code?
A lot of people claim that "comments should explain 'why', but not 'how'". Others say that "code should be self-documenting" and comments should be scarce. Robert C. Martin claims that (rephrased to ...
1
vote
2answers
196 views
How to know whether to create a general system or to hack a solution
I'm new to coding , learning it since last year actually.
One of my worst habits is the following:
Often I'm trying to create a solution that is too big , too complex and doesn't achieve what needs ...
7
votes
2answers
1k views
single for-loop runtime explanation problem
I am analyzing some running times of different for-loops, and as I'm getting more knowledge, I'm curious to understand this problem which I have still yet to find out.
I have this exercise called "How ...
1
vote
0answers
170 views
Complexity limits of solutions created in Google Spreadsheets
I am creating a solution where I essentially put all rules regarding communication with customers (including automatic invoicing, reminder emails, welcome emails, etc.) into a Google Sheets and use ...
0
votes
1answer
865 views
Complexity of ArrayList of LinkedHashSet
I get input strings from the console like this:
while ((currentLine = bufferedReader.readLine()) != null ) {
StringTokenizer string = new StringTokenizer(currentLine, " ");
while ...
0
votes
3answers
238 views
Is there a common programming term for the problems of adding features to an already-featureful program?
I'm looking for a commonly used programming term to describe a software-engineering phenomenon, which (for lack of a better way to describe it) I'll illustrate first with a couple of ...
3
votes
5answers
337 views
Simplicity-efficiency tradeoff
The CTO called to inform me of a new project and in the process told me that my code is weird.
He explained that my colleagues find it difficult to understand due to the overly complex, often new ...
0
votes
1answer
118 views
Time complexity implications when designing shell scripts for large data/high number of files?
There are many questions about the performance of commands or scripts on the U+L SE asset. As time is of the essence, this is often evaluated using the bash time reserved word or the external time ...
-1
votes
3answers
187 views
Is there a metric that can be equated to complexity in laymens terms? [closed]
Often times users cannot comprehend the complexity of software. They think that because a problem is easy to describe then it is easy to solve. I want to equate the complexity of a "simple program" ...
1
vote
1answer
148 views
How to implement an algorithm out-of-core?
I want to implement a parallel clustering algorithm "out-of-core" in CUDA. My CPU has 12GB of RAM and GPU has 4GB of it.
What I want is that the entire dataset should be on the disk, and I can pick ...
2
votes
2answers
189 views
Why must essential mutable derived data have an inverse function?
I was reading the paper Out of the Tar Pit authored by Ben Moseley and Peter Marks when I came across the following section on page 25 regarding essential mutable derived data:
Essential Derived ...
1
vote
2answers
255 views
What are the consequences of Hash-Life running in O(log n)?
After reading about the HashLife algorithm, I found that it runs in O(log n). The Game of Life is also Turing Complete, so in theory we should be able to run any algorithm on a "computer" constructed ...
1
vote
2answers
248 views
What is a O(n) algorithm to solve this puzzle?
We are going to hold a meeting where everybody will speak in clockwise direction around a table. There are n people with n spots. Each person has a position preference (e.g. some want to go first, ...
64
votes
6answers
7k views
How to manage accidental complexity in software projects
When Murray Gell-Mann was asked how Richard Feynman managed to solve so many hard problems Gell-Mann responded that Feynman had an algorithm:
Write down the problem.
Think real hard.
Write down the ...
0
votes
4answers
559 views
Binary Search seems superior, why did the committee of C++ still have Find in the algorithm library?
I wish to search for an integer in a vector of integer. I have two candidates for the job:
Binary Search
Find
It seems that Binary Search is the best candidate for the job as although I have to ...
2
votes
2answers
114 views
Auxiliary space complexity of map vs map!
I'm curious about the difference in space complexity between map and map! in ruby.
If I have the methods:
def mult_by_two(arr)
arr.map {|i| i * 2 }
end
def mult_by_two!(arr)
arr.map! {|i| i * 2 ...
2
votes
4answers
516 views
difference between exponential and logarithmic growth
Why
for(k=1;k<=n;k*=2) grows logarathmically = O(logn)
but I feel it grows exponentially, as the seq look like 1,2,4,8....
and for fibonacci series people say it grows exponentially.
which for me ...
1
vote
2answers
102 views
Is it correct/useful to define Computational Complexity in this way?
I analyzed my algorithm and I deduced that in the best case it requires n^3 iterations while in the worst case it requires n^4 iterations. Then I asserted that my algorithm is in \Omega(n^3) and in ...
2
votes
4answers
3k views
Complexity in nested loops
Foreword:
In this post, I will make the common confusion between O(n) and Theta(n) as complexity notations.
I will write pseudo-code to talk about algorithms, using whatever notation I find to my ...
1
vote
1answer
2k views
Why execution time is different each time in java?
I am trying to make a program in Java which measure the complexity of a specific program with respect to its run time. Let's take a problem and code that problem in all possible ways with respect to ...
0
votes
1answer
107 views
How can I handle clock hands using doubles that suffers at most O(log n) corrupt bits at nth frame of display?
I presently have a clock app that calculates from scratch at every iteration. This means O(1) corrupt bits in my doubles and heavy object creation and deletion as well.
I am wary of running ...
8
votes
2answers
295 views
Should there be a formal role (internal or external) assigned to dev environments to control wasteful complexity?
A few years ago, I worked for a small company that went so far into developing in-house frameworks that they dedicated their most senior developer, and their architect to developing a custom MVC ...
31
votes
3answers
9k views
When is it NOT good to use actors in akka/erlang?
I've been working with akka for 7-8 months now daily.
When I started, I would be working on applications and notice that actors would be used basically anywhere once inside the actor system for ...
