Tagged Questions

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

808 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 ...
186 views

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(...
153 views

Is it possible to have these characteristics in a data structure?

I was tutoring a student that came up with this assignment. It basically requires a data structure with the following characteristics: it holds a set of integers in {1, 2, ..., n} n is power of 2 O(...
64 views

Prove complexity for a generic algorithm

I'm new to theory of complexity and am trying to prove a fact. So, let's consider an algorithm T that receive at input an integer n. That algorithm has a time complexity for n = 1 : θ(1) and for n > ...
401 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 ...
693 views

How can I know when my application is too complex? [closed]

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 ...
771 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; ...
4k 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 ...
113 views

Check in which region is a geoposition Marker located in

I use Mapbox to display some moving markers over a map with several polygons drew over it (feature layers). I have serveral markers (~1000) and multiple feature layers (polygons ~200) that represent ...
220 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 ...
384 views

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 ...
306 views

Should one write Big Oh complexity in the documentation of algorithms? [closed]

When writing or using an algorithm, should the Big Oh complexity be mentioned?
732 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 ...
4k 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 ...
479 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 ...
338 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. ...
170 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 ...
173 views

Burrows-Wheeler transform backward search: how to find suffix index?

BWT backward search algorithm is pretty straightforward if we only need the multiplicity of a pattern. However I also need to find the suffix indices (i.e. positions in the reference string where a ...
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 ...
4k 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 ...
278 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) ...
713 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 ...
522 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 ...
3k 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 ...
298 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, ...
6k 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 ...
3k views

Best resources to really understand run-time complexity [closed]

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 ...
173 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 ...
260 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 ...
6k 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 ...
226 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 ...
400 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 ...
1k 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 ...
61 views

How do I determine correctness of a codes complexity?

Given a piece of code, I may use one of many methods to determine the big O complexity of the code manually (runtime and memory). But, for a given piece of code, how do I determine whether what I ...
105 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 ...
163 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 ...
1k 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 ...
154 views

Time Complexity when Loop Variable Depends upon Outer Loop Variable

What is the time complexity of the following piece of code in worst case? s = 0; for( i = 1; i <= n; ++i ) { for( j = 1; j <= i * i; j++ ) { for( k = 1; k <= j and j % i == 0; k++...
81 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 ...
83 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 ...
442 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 ...
87 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 ...
512 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 ...
13k 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 ...
5k 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 ...
449 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 ...
280 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, ...
3k 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 ...
280 views

How to write highly changeable, highly complex software? [closed]

I know questions like this has been asked before. But none of them truly answered me. How to keep a big and complex software product maintainable over the years? How do you organize highly customized ...
200 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 ...