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
6
votes
0answers
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],...
4
votes
0answers
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 ...
4
votes
1answer
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 ...
3
votes
0answers
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, ...
3
votes
0answers
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 ...
3
votes
0answers
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 ...
2
votes
1answer
49 views

Using Python to search a sorted 2D Matrix

Code Problem ...
2
votes
0answers
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 ...
2
votes
0answers
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 ...
2
votes
1answer
61 views

Modelling Immerman–Szelepcsényi in Haskell

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. ...
2
votes
0answers
192 views

MergeSort linked list implementation

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 ...
2
votes
0answers
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 ...
2
votes
0answers
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 ...
2
votes
0answers
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 ...
2
votes
0answers
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 (...
2
votes
0answers
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 ...
2
votes
0answers
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 (...
2
votes
0answers
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 ...
1
vote
0answers
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(\...
1
vote
0answers
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. ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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,...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
71 views

A scalable function for get boundary vertices in a graph

Given a community division I need a list of vertices that have edges in more than one community, i.e., boundary vertices. I've tried this: ...
0
votes
0answers
13 views

Simplifying code for deleting directories

Background info: An FSObject is a dir or a file. The structure definition for a directory (dir) is the following (define-struct dir (name owner contents)). A ...