The complexity tag has no wiki summary.
0
votes
3answers
163 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
122 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
115 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 ...
0
votes
2answers
120 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
189 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, ...
51
votes
6answers
4k 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
282 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 ...
1
vote
2answers
47 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
284 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
93 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
1k 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
625 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
89 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
282 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 ...
13
votes
3answers
3k 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 ...
4
votes
6answers
297 views
Fields vs method arguments [closed]
I just started writing some new class and it occurred to me that I was adding a lot of method arguments that are not strictly needed. This is following a habit to avoid having state in classes that is ...
0
votes
0answers
75 views
why the time complexity of Quick sort is better than heap sort and merging sort? [duplicate]
the heap sort\Merging sort\Quick sort all have the same time complexity nlogn.
why the quick sort is better than others?
-4
votes
4answers
227 views
Which if statement requires less computation?
I have
if (!b && c || a && c)
//do action a
else
//...
Due to some internal relationship between a, b, and c. !b && c || a && c is proved to be equivalent to (! ...
5
votes
2answers
259 views
Does increasing the number of classes increase code complexity? [duplicate]
To illustrate the question, let's say we have two programmers of comparable skill that both solve the same problem. The code they turn out has roughly the same lines of code, but one programmer uses 5 ...
11
votes
3answers
568 views
Do teams get more productive by adding more developers? [duplicate]
Suppose you've got a project that is running late. Is there any proof or argument that teams become much more productive by adding more people? I am looking for answers that can be supported by facts ...
35
votes
4answers
2k views
Can too much abstraction be bad?
As programmers I feel that our goal is to provide good abstractions on the given domain model and business logic. But where should this abstraction stop? How to make the trade-off between abstraction ...
2
votes
1answer
126 views
What's the computational complexity of the Groovy unique() method?
Question 1
What's the computational complexity of the Groovy unique() method?
Question 2
How could I have figured it out by myself? The unique() method is defined in the class DefaultGroovyMethods. ...
2
votes
1answer
978 views
What is the time complexity of the algorithm to check if a number is prime?
What is the time complexity of the algorithm to check if a number is prime?
This is the algorithm :
bool isPrime(int number){
if(number < 2) return false;
if(number == 2) return true;
if(number ...
15
votes
12answers
4k views
Is it possible to reach absolute zero bug state for large scale software?
I am talking about 20-30+ millions lines of code, software at the scale and complexity of Autodesk Maya for example.
If you freeze the development as long as it needs to be, can you actually fix all ...
2
votes
3answers
486 views
Limit useless complexity in code [duplicate]
I have a question, to explain that, what better than an entirely fictional example?
Let's say you are a young developer just being employed in a firm.
All data is stored in a huge database (let's ...
-2
votes
1answer
222 views
Algorithm Correctness and Complexity Analysis [closed]
If given an algorithm to traverse a graph (say with a breadth first traversal algorithm). And say you code it in the same manner described in this video tutorial shows (starting at 04:30 for breadth ...
1
vote
3answers
314 views
What can Go chan do that a list cannot?
I want to know in which situation Go chan makes code much simpler than using list or queue or array that is usually available in all languages.
As it was stated by Rob Pike in one of his speeches ...
4
votes
2answers
413 views
Is currying too complex a tool to actually use?
Today I feel like I finally grokked currying (in Javascript), and of course, like any programmer who has learned a new trick, my mind immediately began racing over how to improve my current codebase ...
7
votes
1answer
1k views
Problems Calculating Big-O Complexity
I'm a complete beginner to Java, only in my second quarter of classes. I'm having trouble understanding our current chapter about calculating big-O for methods. So I thought I was right in saying that ...
3
votes
3answers
343 views
Is unconditional code considered a branch?
Having simple code like this:
int A=5;
object X=Console.ReadLine()
if(Condition)
DoSomething();
else
DoStuff();
DoSomethingElse();
Some sources say there are actually 4 branches: First ...
6
votes
4answers
423 views
Good idea to move logic out of SQL statements?
I'll preface this question by saying that I am very new to professional software dev.
I work on a team that takes data in from other groups in my company and turns this data into reports usable by ...
10
votes
2answers
318 views
Dealing with Feature Intersections
I have recently witnessed more and more problems similar to the ones explained in this article on feature intersections. Another term for it would be product lines, though I tend to attribute these to ...
11
votes
6answers
461 views
Guidance in naming awkward domain-specific objects?
I'm modeling a chemical system, and I'm having problems with naming my elements / items within an enum.
I'm not sure if I should use:
the atomic formula
the chemical name
an abbreviated chemical ...
3
votes
2answers
465 views
Too complex/too many objects?
I know that this will be a difficult question to answer without context, but hopefully there are at least some good guidelines to share on this. The questions are at the bottom if you want to skip the ...
10
votes
1answer
805 views
Computational Complexity of Correlation in Time vs Multiplication in Frequency space
I am working with 2d correlation for image processing techniques (pattern recognition etc...). I was wondering if there is a theoretical approach on how to tell when to use multiplication in frequency ...
2
votes
2answers
194 views
Using Completed User Stories to Estimate Future User Stories
In Scrum/Agile, the complexity of a user story can be estimated in story points. After completing some user stories, a programmer or team of programmers can use those experiences to better estimate ...
5
votes
1answer
526 views
How can I compute the Big-O notation for a given piece of code? [closed]
So I just took a data structure midterm today and I was asked to determine the run time, in Big O notation, of the following nested loop:
for (int i = 0; i < n-1; i++) {
for(int j = 0; j < ...
0
votes
2answers
221 views
Why the bound of a linear function is same as that of a quadratic equation
I am learning algorithms, and I came across something very interesting.
The asymptotic bound of the linear equation (a * n)+b is O(n^2), for all a > 0.
This is same bound as a * n^2 + b * n + c, ...
6
votes
1answer
364 views
Complexity of a web application
I am currently writing my Master's Thesis on maintainability of a web application. I found some methods like the "Maintainability Index" by Coleman et.al. or the "Software Maintainability Index" by ...
8
votes
2answers
2k views
What does it mean by expected running time and average runnnig time of an algorithm?
Let's say we want to analyze running time of algorithms. Sometimes we say that we want to find the running time of an algorithm when the input size is n and for the worst possible case it is denote it ...
3
votes
1answer
2k views
What does it mean when we say that some function is polynomially bigger/smaller than some other function?
I was going over this video lecture on master theorem from Introduction to Algorithm and while explaining case A of the master theorem professor says that some function f(n) is polynomially smaller ...
3
votes
4answers
375 views
Do large test methods indicate a code smell?
I have a particular method called TranslateValues() (Cyclomatic-Complexity of 5) which I would like to test.
The test requires a substantial number of mock objects which take up most of the method; ...
1
vote
3answers
2k views
Big O(n log n) and Quicksort number of operations
I have an Array with 1,000,000 unsorted elements. I need to calculate expected number of operations that needs to be performed to sort array using Quicksort algorithm in common situations (not the n^2 ...
14
votes
5answers
2k views
What would be the Impact of P=NP? [closed]
I am preparing for a test and I can't find a clear answer on the question: What would be the impact of proving that PTIME=NPTIME. I checked wikipedia and it just mentioned that it would have "profound ...
1
vote
6answers
6k views
Merge sort versus quick sort performance
I have implemented merge sort and quick sort using C (GCC 4.4.3 on Ubuntu 10.04 running on a 4 GB RAM laptop with an Intel DUO CPU at 2GHz) and I wanted to compare the performance of the two ...
10
votes
5answers
10k views
Determining if an Algorithm is O (log n)
I'm refreshing my CS Theory, and I want to know how to identify that an algorithm O (log n) complexity. Specifically, is there an easy way to identify it?
I know with O(n), you usually have a single ...
3
votes
1answer
3k views
Magic square check for N×N matrix with minimum complexity
Is there any algorithm that works better than O(n²) to verify whether a square matrix is a magic one (e.g. such as sum of all the rows, cols and diagonally are equal to each other)?
I did see someone ...
3
votes
3answers
1k views
How to describe the complexity of a project, without revealing information?
I will be looking for a job after a long break, so I need all the help I can get.
Problem is, my best point in a portofolio is an unusual application, using quite unusual algorithms, that may seem ...
5
votes
3answers
502 views
How to simplify my complex stateful classes and their testing?
I am in a distributed system project written in java where we have some classes which corresponds to very complex real-world-business objects. These objects have a lot of methods corresponding to ...
19
votes
8answers
1k views
Adding complexity to remove duplicate code
I have several classes that all inherit from a generic base class. The base class contains a collection of several objects of type T.
Each child class needs to be able to calculate interpolated ...
