The complexity tag has no wiki summary.
1
vote
1answer
198 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 ...
-1
votes
0answers
90 views
Time complexity (in big-O notation) of the following recursive code? [closed]
public static int abc(int n) {
if (n <= 2) return n;
int sum = 0;
for (int j=1; j<n; j *= 2)
sum += j;
for (int k=n; k>1; k /= 2)
sum += k;
return abc(n ...
1
vote
10answers
1k views
Is it possible to reach absolute zero bug state for large scale software? [closed]
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
426 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
106 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 ...
0
votes
1answer
156 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 ...
-5
votes
2answers
72 views
Client-side technology stack optimized for durability [closed]
So what's a developer to do when he wants to start a complex long-term project (say 30 years) which is mostly client-side GUI with some logic thrown in and doesn't want to rewrite it every year or ...
4
votes
2answers
381 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
537 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
272 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
317 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 ...
9
votes
2answers
297 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
419 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
290 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
250 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 ...
3
votes
2answers
151 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 ...
2
votes
1answer
428 views
What is the Big-O time complexity of this algorithm [closed]
I was wondering what the run time of this small program would be?
#include <stdio.h>
int main(int argc, char* argv[]) {
int i;
int j;
int inputSize;
int sum = 0;
if(argc == 1)
inputSize ...
5
votes
1answer
347 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
184 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
262 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
720 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 ...
2
votes
1answer
680 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
221 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
1k 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
896 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
3k 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 ...
9
votes
5answers
4k 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
2k 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
753 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 ...
3
votes
3answers
292 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 ...
17
votes
8answers
995 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 ...
6
votes
4answers
1k views
Smallest lexicographical rotation of a string using suffix arrays in O(n)
I will quote the problem from ACM 2003:
Consider a string of length n (1 <= n <= 100000). Determine its minimum lexicographic rotation. For example, the rotations of the string “alabala” ...
2
votes
1answer
440 views
Best Upper Bound & Best Lower Bound of an Algorithm
I am studying for a final exam and I came past a question I had on an earlier test.
The questions asks us to find the minimum value in an unsorted array of integers. We must provide the best upper ...
9
votes
7answers
275 views
When should complexity be removed?
Prematurely introducing complexity by implementing design patterns before they are needed is not good practice.
But if you follow all (or even most of) the SOLID principles and use common design ...
18
votes
3answers
277 views
Is there a correlation between complexity and reachability?
I've been studying cyclomatic complexity (McCabe) and reachability of software at uni recently. Today my lecturer said that there's no correlation between the two metrics, but is this really the case?
...
1
vote
1answer
102 views
Algorith analysis refresher help
I haven't touched algorithm complexity stuff in quite a while, so I am trying to do a refresher.
I am trying to figure out the number of steps in the following for loop.
for(i = 0; i < n; ...
3
votes
5answers
358 views
How can I know when my application is too complex?
I'm currently working on my own project for an Android app, but then as time goes it feels like my app is concentrating more on another feature than what I had in mind when I first design the app.
So ...
3
votes
4answers
230 views
Efficiently implementing a prime sieve [closed]
I've been trying to solve a class of problems that require the generation of 1st n prime numbers. Now, n may be large, so completely fitting (2..n) in memory as required by some sieve techniques isn't ...
9
votes
5answers
378 views
Is the concept of computational complexity important for software developers?
I was under the impression that the concepts of time and memory complexity are a must for graduates of compsci courses, but having studied engineering I have no knowledge if that is the case. I have ...
2
votes
1answer
905 views
How costly are the Python dict and set in-built types?
I have undertaken a project concerning database deduplication. I did some research and have found that the Python dict type actually is a hashmap that uses open addressing.
In the deduplication ...
2
votes
6answers
862 views
Why is the formal definition of Big O notation formulated as such?
Consider the formal definition:
f(n) = O(g(n))
Why is it not:
f(n) = O(f(n))
or
f(n) = O(c*f(n))
since for the Big O analysis, f(n)=2n and g(n)=n are identical?
I am ...
4
votes
4answers
1k views
Big-O for nested loop
I am reading this post on Big-O
It says that the following code is O(n^2):
bool ContainsDuplicates(String[] strings)
{
for(int i = 0; i < strings.Length; i++)
{
for(int j = 0; j ...
2
votes
4answers
474 views
Difference between complexity and performance guarantee
I'm a bit confused with the performance guarantee and complexity of selection sort.
I checked through internet and the complexity of selection sort is O(n^2). This O(n^2) is in terms of time ...
2
votes
6answers
206 views
Complexity vs maintainability in modern hardware
Today with the modern hardware and memory coming cheap, how much sense does it make to spend effort to analyze algoriths or data structure complexity?
Wouldn't it be better instead, to focus on clean, ...
4
votes
2answers
198 views
Is there a correlation between code complexity and developer productivity?
Is the time spent refactoring a code base worth it in the long run, in terms of developer productivity?
It seems pretty clear to me that modifying a clean, well designed system is much simpler and ...
1
vote
2answers
202 views
complexity of suffix tree question [closed]
Build a suffix tree from a string.
While creating the suffix tree, count re-occurrences of every substring and save it on the number of occurrences on the node.
Then do a BFS search on the tree (from ...
12
votes
7answers
2k views
What is O in Big O?
What is Big and O in Big O notation? I've read the definitions and it doesn't tell what is O pronounced as 'oh'. For example - I understand that O(n) is complexity of a linear algorithm where n could ...
6
votes
1answer
394 views
Space complexity of Iterative Deepening DFS
We read on Wikipedia > Iterative deepening depth-first search that
The space complexity of IDDFS is O(bd), where b is the branching factor and d is the depth of shallowest goal.
Wikipedia also ...
2
votes
2answers
805 views
Best resources to really understand run-time complexity
I'm familiar with the basics of run-time analysis such as what makes certain types of code O(n) and O(n^2). But I'm having real trouble learning, understanding, and really remembering how to analyze ...
1
vote
2answers
149 views
Would a computer engineering degree involve complex event processing?
I've recently discovered the awesomeness of Complex event processing. Just reading the wikipedia page gave me chills on how this technology could be used and evolved into something very powerful.
I'm ...
