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.
7
votes
4answers
882 views
Checking if three numbers sum to a given number
I'm working on the following interview practice problem, and got the following solution, which runs in worst case n! time (best case constant), and I'm trying to optimize it.
Can you offer any ...
4
votes
1answer
54 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 ...
26
votes
11answers
2k views
Searching in an array in less than O(n) time
I've an array where each element is either one less or one greater than the preceding element. I've to search an element in it in less than O(n) time. I've implemented it like this:
public int ...
2
votes
1answer
52 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 cube1: {a, b, c} and ...
4
votes
1answer
51 views
Using Guava to reduce code complexity (and possibiliy to improve readability) of null check and assign default value
Below is my java code with some complexity,
String input;
double a;
if (null != input && !input.isEmpty()) {
a = Double.parseDouble(input);
} else {
a = defaultValue;
}
With Guava, ...
3
votes
5answers
163 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: i == list[i] (where i is the index 0 <= i <= len(list)).
def ...
1
vote
3answers
59 views
Find all consecutive sequences in an ordered set
I have the following set. a = [1,2,3,4,5] and i want to find all of the following sequences of consecutive elements:
1,
1,2
1,2,3
1,2,3,4
1,2,3,4,5
2,
2,3,
2,3,4,
2,3,4,5
3,
3,4
3,4,5
4
4,5
5
This ...
0
votes
2answers
529 views
Codility Fish Question O(N)
I understand that if you don't know the trick, it's not easy create a solution with a complexity of O(N). However, I would like to ask you how to solve this tricky question:
You are given two ...
2
votes
0answers
35 views
TLE for SPOJ Upper Right King
I am solving this problem on SPOJ Upper Right King (Hard).
I've written a solution in Python with a time complexity of O(n(logm)2). But it's showing TLE. Can anyone help me out with this?
For more ...
5
votes
1answer
90 views
Finding an efficient algorithm in terms of reducing Big O complexity
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 ...
4
votes
4answers
120 views
Reduce complexity of state machine method
I've asked Code Climate to generate metrics for the ftpd Ruby gem. It correctly identified the God class; I know what to do about that. But one of the smaller classes has me stumped. This is ...
6
votes
1answer
492 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 ...
2
votes
2answers
378 views
Fibonacci sequence implementation
This was too slow for my computer:
int f(unsigned int x)
{
if(x <= 1) return 1;
else return f(x-1)+f(x-2);
}
/* main */
int main()
{
for(int i = 0; i < 50; i++) cout << f(i) ...
0
votes
0answers
123 views
Could someone profile the space and time complexity of this Haskell snippet?
I'm new to programming and even more new to Haskell, below is a little tid-bit I wrote that operates on a bunch of lists. I am wondering if someone would be kind enough to walk through the function ...
3
votes
2answers
259 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 ...
7
votes
3answers
202 views
Can anyone make my O(n^3) function more efficient, or offer suggestions to make handling it more efficient?
I'm trying to devise a way to calculate the mean differences (the absolute average differences between any two values in a set), of sub-arrays (starting from arbitrary indices) in an int array. I'll ...
