Complexity deals with various forms of calculating the complexity of code. Cyclomatic complexity, n-path complexity, Big O time and space complexity.

learn more… | top users | synonyms

3
votes
3answers
397 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 ...
3
votes
1answer
3k 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
1answer
193 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. ...
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 ...
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 ...
2
votes
6answers
2k 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 ...
2
votes
5answers
301 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 ...
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 ...
2
votes
4answers
272 views

Process each row against each other, how much would it cost?

If I have n rows in a database, and I want to compare every row against each other, how many loops (or processes) would I need to do. Is it n2? (so if I have 30,000 rows then it would be 900,000,000) ...
2
votes
4answers
408 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 ...
2
votes
3answers
507 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
3answers
2k views

c++ write own xml parser vs using tinyxml

I am currently in a task to generate an XML file for an srt text file containing timestamps and corresponding text. To generate an exe file which accepts file name input and outputs the relevant XML ...
2
votes
6answers
268 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, ...
2
votes
1answer
2k 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 ...
2
votes
3answers
100 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 ...
2
votes
2answers
228 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
3k 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
2answers
2k 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 ...
2
votes
2answers
157 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 ...
2
votes
4answers
815 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
1answer
59 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 ...
2
votes
2answers
160 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
2answers
91 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
1answer
959 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 ...
2
votes
1answer
71 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 ...
2
votes
2answers
452 views

How do we know if a problem is hardest in NP

I read that the definition of NP-complete is : These are the hardest problems in NP. Such a problem is NP-hard and in NP How do we know if a problem is hardest in NP, and no harder problem ...
2
votes
1answer
93 views

Best data structure to store data sorted alphanumerically AND by weight

What is the best data structure to store data sorted alphanumerically AND by weight (where weight is the first sorting criterion) with very low access time probably Olog(n) or better Application: A ...
1
vote
3answers
4k 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 ...
1
vote
7answers
10k 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 ...
1
vote
3answers
383 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 ...
1
vote
2answers
237 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, ...
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 ...
1
vote
4answers
133 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
2answers
190 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 ...
1
vote
1answer
161 views

Algorithm 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; ...
1
vote
1answer
188 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 ...
1
vote
3answers
114 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 ...
1
vote
2answers
164 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 ...
1
vote
2answers
200 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
99 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 ...
1
vote
1answer
143 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 ...
1
vote
0answers
58 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
0answers
116 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
4answers
417 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 ...
0
votes
2answers
259 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, ...
0
votes
3answers
228 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 ...
0
votes
1answer
135 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 ...
0
votes
1answer
106 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 ...
0
votes
1answer
91 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 ...
0
votes
1answer
171 views

Whole Solution Complexity … vs Development Complexity

I am generally a PHP Developer that deals in a few different MVC frameworks. I am being tempted (like most) to break out of my comfortable LAMP environment in pursuit of a "prettier" and "more ...