Software Engineering Stack Exchange
Software Engineering Stack Exchange

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.

Complexity takes many forms within computing. Most often it is used as an attempt to measure either how hard something is to understand, or how long (or large) something will run.

The understanding complexities that are used most often are that of cyclomatic complexity which looks at the number of independent paths through some code, and n-path complexity (more often seen in static analyzers) that looks at the combination of all the different paths throughout the code.

Related reading:

The more theoretical complexity is that of big O and is used with the asymptotic behavior of either the time code will take to run, or the amount of memory it will use.

Related reading:

221 questions
91
votes
10 answers

How to explain why multi-threading is difficult

I am a fairly good programmer, my boss is also a fairly good programmer. Though he seems to underestimate some tasks such as multi-threading and how difficult it can be (I find it very difficult for anything more than running a few threads, waiting…
Mr Shoubs
  • 841
  • 1
  • 8
  • 12
79
votes
15 answers

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 the bugs until there is simply not a single bug,…
Joan Venge
  • 1,950
  • 2
  • 18
  • 24
78
votes
7 answers

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 solution. Gell-Mann was trying to explain that…
user7146
68
votes
5 answers

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 communicating between most objects. So I did the same -…
JasonG
  • 1,129
  • 1
  • 10
  • 14
67
votes
17 answers

Is big-O really that relevant when working in industry?

In every interview I have been in, I have been quizzed on mathematical analysis of complexity, including big-O notation. How relevant is big-O analysis to development in industry? How often do you really use it, and how necessary is it to have a…
MM01
  • 1,373
  • 2
  • 14
  • 13
62
votes
4 answers

Trying to understand P vs NP vs NP Complete vs NP Hard

I am trying to understand these classifications and why they exist. Is my understanding right? If not, what? P is polynomial complexity, or O(nk) for some non-negative real number k, such as O(1), O(n1/2), O(n2), O(n3), etc. If a problem belongs to…
Nakano
  • 731
  • 1
  • 6
  • 7
61
votes
7 answers

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 and all it's benefits (flexibility, ease of…
Random42
  • 10,370
  • 10
  • 48
  • 65
59
votes
6 answers

Why aren't there code overviews for open-source projects?

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 changing one line of code at a big project you have…
fiatjaf
  • 727
  • 5
  • 11
41
votes
2 answers

What is O(...) and how do I calculate it?

Help! I have a question where I need to analyze the Big-O of an algorithm or some code. I am unsure exactly what Big-O is or how it relates to Big-Theta or other means of analyzing an algorithm's complexity. I am unsure whether Big-O refers to the…
mowwwalker
  • 1,117
  • 2
  • 12
  • 20
33
votes
5 answers

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 loop; O(n^2) is a double loop; O(n^3) is a triple…
Atif
  • 915
  • 1
  • 6
  • 12
31
votes
7 answers

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 be the number of operations. but what is an O?
Karen15
  • 329
  • 1
  • 3
  • 4
25
votes
9 answers

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 values from the collection of objects, but since the…
Phil
  • 3,660
  • 26
  • 29
21
votes
6 answers

Using a different algorithm depending on the size of the input

I recently finished a course on advanced algorithms, and another on complexity & computability theory, and in the past few days my mind has been somewhat preoccupied by this question. Why don't we just use a different algorithm based on the size of…
cliesens
  • 345
  • 2
  • 6
19
votes
6 answers

What do you call it when you change the Big O execution time of a function

Let's say I have a function which sorts a database in O(n^2) time. I want to go about refactoring it so it runs in O(n log(n)) time, and in doing so I will change the fundamental way the operation runs, while keeping the return values and inputs…
Code Whisperer
  • 723
  • 6
  • 10
19
votes
16 answers

Do else blocks increase code complexity?

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.. Color is of a unique type string…
Selali Adobor
  • 639
  • 4
  • 14
1
2 3
…
14 15