A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

# Questions tagged [complexity]

Complexity is the analysis of how the time and space requirements of an algorithm vary according to the size of the input. Use this tag for reviews where the "Big O" is a concern.

342 questions
Filter by
Sorted by
Tagged with
1k views

97 views

### Joining collections… because it's fun

I'm working on a LinqEnumerable class (reviewable here), and I'm no Big-O expert and I'm pretty bad with algorithms, so I wonder what the complexity is for what I'...
3k views

### Finding the longest unique sub-string in a string

I recently interviewed with a company for software engineering position. I was asked the question of finding the longest unique sub-string in a string. My algorithms was as follows: Start from the ...
364 views

### Fastest way to find maximum deviation

I acknowledge that this exact question was asked here. I was working on the same problem from the same website. I had the same question and consulted the above as a reference, however with respect ...
5k views

### Print all nodes from root to leaves

I've made a function to print all paths from root to all leaves in a binary search tree. I already have an insert function, which I haven't included in the code here as I felt it was irrelevant to the ...
2k views

### Time complexity of anagram solution

I have written code to return anagrams from a list of words. I'm a newbie in time complexity analysis so pardon my ignorance if this is a blatantly obvious question. Am I right in thinking this is in ...
334 views

### Interview task to efficiently find compact representation of nodes in tree and find big O time

I recently had an interview problem where I was asked to find a compact representation of nodes in a tree. As an example, consider the following tree: ...
166 views

### Time complexity of 0/1 Knapsack challenge

The code gives correct output. How do I calculate time complexity for code like this? The program finds all the combinations of items and sees if the combination gives the max profit. If the last ...
2k views

### “Magic Fraction” finder

A Magic Fraction for N is one that has the following properties: It is a proper fraction (the value is < 1) It cannot be reduced further (the GCD of the numerator and the denominator is 1)...
91 views

### Two squares or not two squares - constant time optimization

I have been trying to solve this problem, and after a bit of googling, I realised a $O(\sqrt{n})$ time complexity works fine (though the algorithm suggested is different from that I have used). My ...
4k views

### Is this a good Ruby implementation of Prime Factorization?

I'm doing some practice problems on Khan Academy. The current one is Prime factorization. I came up with this: ...
2k views

### Construct KD-Tree in Java

I want to construct KD-Tree from unsorted List of points in the plane (i.e. 2-KD-Tree). To do so I used the method from Wikipedia: http://en.wikipedia.org/wiki/Kd-tree#Construction This is my code: <...
1k views

### Russian doll envelops

Interview question from the interwebz You have a set of envelopes of different widths and heights. One envelope can fit into another if and only if both the width and height of one envelope is ...
1k views

### Finding largest subset of line segments that don't intersect

I completed a challenge of codeeval called BayBridges. It can be found here. I have uploaded my code on GitHub here. In summary, the challenge is to take a list of line segments, each specified by ...
700 views

### Psycho and ordinary numbers

The problem statement can be found here. In short, here's what the problem is about: You're given a set of numbers and you need to find whether the the numbers are ordinary or psycho. For a number ...
41 views

### Proving a conjecture given a set of clauses - calculating complexity

I have written this Perl program to prove a conjecture given a set of clauses. I've actually posted some code from it on here in another question. This time its all done and I've made it as fast as ...
2k views

### Simplify function to sum the absolute value of the difference between all pairs of elements of a sorted array

Given a sorted array of N elements, I need to find the absolute sum of the differences of all elements. Given 4 elements (1, 2, 3 and 4): |1-2|+|1-3|+|1-4|+|2-3|+|2-4|+|3-4| = 10 Here is my code ...
103 views

### Calculate difference of indices

The challenge is to reconstruct an n-digit number using the following information: On each step, you choose an index x from 1 to n. For all indices y (y < x), you calculate the difference by =...
717 views

### Longest 'balanced' substring

I was given a task where given a string of '0's and '1's, return the longest substring where the count of '0's and '1's are equal. I was told also that the code should be O(n) and space O(1). Below ...
330 views

### Performance analysis of 3 digits sum

I have a method that finds 3 numbers in an array that add up to a desired number. ...
429 views

### Determine total number of ways of reaching a destination

Question: One of Scotland Yard’s most wanted criminal (Mister X) is on the run and needs to reach a certain destination safely. There are three modes of transport available for him - By air, ...
1k views

### Refactoring my problem-solution to reduce complexity

I need some help refactoring my solution to the problem below: Problem Statement An Association of Computer Scientists meets on a weekly basis. There is a certain number of seats in the meeting ...
1k views

...
2k views

### Big-O complexity calculation for a merge and sort function

I have the following code which basically takes a list of sorted integer arrays and merges them together removing the duplicates. I have tried to do the complexity analysis and came to a rough ...
369 views

### Reducing complexity of method

I'm trying to reduce the complexity of some methods, and I'm not exactly sure what approach to take. I'm currently building a PHP wrapper for a REST API, and the main problematic class is here: https:...
4k views

### Permutation of given string

I am reading a book on DSA, and the author explains how to generate the permutation of strings using recursion. I want to know if there are better ways of doing the same, unless this is the best ...
300 views

### Is this an efficient merge sort implementation with regards to average time complexity in Big-O notation?

Is my below merge sort implementation in O(n log n)? I am trying to implement a solution to find k-th largest element in a given integer list with duplicates with O(N*log(N)) average time complexity ...
10k views

### Fibonacci sequence implementation

This was too slow for my computer: ...
153 views

### Given set of cubes can we get a given word?

Given some cubes, can cubes be arranged such that an input word can be formed from the top view of the cubes? For example: assume an imaginary cube with only 3 surfaces where ...
852 views

### Not getting Log(n) performance from quadtree

Here is my QuadTree class and node. The problem is really with Querying. In my game, I have a city which can have n * n streets (randomly generated). And each street has buildings. What I do is put ...
2k views

### count all array[index] == index occurrences

The method foo gets a sorted list with different numbers as a parameter and returns the count of all the occurrences such that: ...