# 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.

353 questions
Filter by
Sorted by
Tagged with
1k views

### Codility MaxCounters peformance in Python capping out at 77% performance

My problem is quite similar to the question found here, except I am attempting to answer the question in Python. Given an array of N counters, all initialized to 0, and an array ...
7k views

### PermCheck Codility with time complexity of O(N)

I have this solution for Codility's PermCheck problem. In summary, the task is to check whether array A contains each number in $1 \ldots N$ exactly once. I got ...
13k views

### Permutations of any given numbers

I have solved one programming problem where we have to find all the permutations of given numbers. For example, $[1,2,3]$ have the following permutations: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,...
2k views

### Finding unique triplets adding up to 0

I am working on a problem "3Sum", in which, given an array S of n integers, are there elements ...
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 ...
3k views

### Re-arrange a string into a { consonant, vowel, consonant, vowel … } sequence

I was prompted to give someone advice about the following problem: Given a string with equal amount of vowels and consonants, re-arrange it so that it follows the sequence { consonant, vowel, ...
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 ...
365 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 ...
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 ...
8k views

### Finding the largest repeating substring

Here's my code that takes a large string, and searches for the longest reoccurring substring. It compares the first letter with every other until it finds a match, then saves it. Then it compares the ...
167 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 ...
141 views

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 ...
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 ...
10k views

### Fibonacci sequence implementation

This was too slow for my computer: ...