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

29 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
552 views

### Intersection of two lists in Python

I am currently working on an algorithm, which involves finding the intersection of two lists. That is, given the following inputs [1,2,2,1],...
50 views

### Coordination function

This function started very clean but I had to add requirements: Added a Stopwatch to only update the caller periodically. I guess that responsibility could be ...
99 views

### Time(n) Complexity of Fibonacci Algorithms

It is my first use of classes in Python. I wanted to create something useful and try some new things as I learn this cool language: strategy pattern, testing with nanoseconds precision, curve/poly ...
96 views

### Calculating the total sum of inversion count for all subarrays

My approach was to visit all inversion count pair and count how many subarrays these pair contribute. Visiting every pair requires $\mathcal{O}(n^2)$ time, but I want an optimized version of this, ...
502 views

### Finding the majority element in a sequence of integers in $O(n \log n)$

I wrote this piece of code as solution to a problem set that required finding the majority element in a list using divide and conquer in $O(n \log n)$. The majority element is defined as the ...
142 views

### ACM-ICPC HackerRank challenge in C++

I was doing a programming question in C++ at HackerRank. Given a set of up to 500 bitstrings, each up to 500 bits long, the task is to find the pair a and b such that the bitwise OR contains the most ...
49 views

Code Problem ...
30 views

### Snake string implementations

This snippet uses a string as an output. As we iterate through the input string, I just keep appending a character to the string and I know this just pretty much creates a new string everything I add ...
111 views

### Frog Jump time complexity

I have tried to work out the Frog Jump task on Codility. The algorithm for solving this is rather simple but the maximum score I am able to achieve is 55% (also 44% with modulus operations). A ...
61 views

I am trying to model the proof of Immerman–Szelepcsényi Theorem with Haskell since it heavily uses non-determinism. An explanation of what the point of this is can be found here. ...
192 views

I wrote a MergeSort implementation of doubly linked list, based on the MergeSort implementation of array on the textbook Algorithms 4th, which is definitely $O(n \log n)$. I think my linked list ...
39 views

### Find target in sorted array pivoted at some unknown point in O(log n)

You are given an array sorted in ascending order which is rotated at some pivot unknown to you beforehand. Find your target in $O(log n)$ which means it should be a binary search. If the value ...
40 views

### Method that adds edges to a graph until all nodes have the given degree

Exercise 2-3 in Think Complexity: Complexity Science and Computational Modeling by Allen B. Downey asks us to implement a method for a class of undirected graphs: Write a method named ...
48 views

### RTB, SSPs is True 2nd Price Auction Program

I've created this program that is intended to check if SSPs in RTB auctions run true second price auction. The program is running properly and returning the values as desired. I would like to get ...
856 views

### Word Wrap via Dynamic Programming

Word Wrap problem in short: Given n words and a line length, break the words into lines in such a manner that minimizes the sum of the costs of all the lines. Consider the cost of each line being (...
212 views

### Improving time efficiency of finding maximum area rectangles in a histogram

Here's my solution but I am looking for ways to improve the time complexity of solution. Also this question is categorized as being solved by stack so I would like to know how to approach it using ...
57 views

### Byzantine payment processing code

I've been working on a large Ruby on Rails application for several years. We inherited it and refactored and upgraded it, but there are some sections that have not been touched in at least 5 years (...
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 ...
38 views

### Binary Heap module in Typescript/Javascript supporting min-heap and max-heap

About binary heaps: https://en.wikipedia.org/wiki/Binary_heap The purpose of this module is to allow quick and efficient priority queue management, compared to linked list. Efficiency: insert: \\$O(\...
38 views

### leetcode 230: kth smallest element in a Binary Search Tree

Here is my implementation: the goal of the algorithm is to find the kth smallest element in a BST. ...
116 views

### Codility Tape Equilibrium

This question is related to this one, since it's about the same Codility exercise (Tape Equilibrium instructions): Time complexity of tape equilibirum Basically, given an integer array, the objective ...
36 views

### Mixed Duo String Generator Part 2

Mixed Duo String Generator Hello again; Previously my code was critique and I applied this feedback to form my new revised code for the Mixed Duo String Generator. In the code below I revised it to ...
1k views

### Find the length of minimum sub array with maximum degree in an array

I tried solving a problem in Hackerrank which is to find the length of minimum sub array with maximum degree in an array. For example, consider the example {2, 2, 1, 2, 3, 1, 1} the min sub-array ...
205 views

### Parsing URL query strings in AngularJS

Here are two very small blocks of code I wrote while trying to fix a bug in AngularJS. Both do the same thing. I'm trying to understand how the two differ, mainly in terms of the tradeoff between cpu ...
76 views

### One-off string detection

Problem spec from CareerCup. Given two strings, return boolean True/False if they are only one edit apart. Edit can be insert/delete/update of only one character in the string. Eg. True xyz,xz xyz,...
85 views

### SPOJ Aliens in a Train

I need to find the largest interval with a value less than a limit Lt. The data is as follows: For every test case T: Number of elements N, limit Lt N number of elements data I wrote the ...
2k views

### DP algorithm to find minimum average wait for customer-serving system

Below is the code to find the minimum average waiting time for customers at a store. I want improve the time complexity of the code. As an overview of the logic, I start from ...