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

28 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
63 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 ...
• 371
198 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 ...
• 141
121 views

### Benchmarking multiple implementations of a Code Kata: queue for the self-checkout tills at the supermarket

I was reading this question: Why is my function timing out when run with a larger data set? And although I couldn't quite grasp the OP's implementation and so didn't feel like answering. I did some ...
• 5,387
293 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, ...
• 31
666 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 ...
191 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 ...
112 views

### Monotonic stack - complexity analysis

I tried following the official solution of LC975 (https://leetcode.com/problems/odd-even-jump/), using a monotonic stack - i.e., I reimplemented their solution (Approach 1) from python in C++. TLDR ...
• 322
186 views

• 11
1 vote
87 views

### Sorting Algorithm using Modified Merge sort

I've been messing around with merge sort. Instead of doing a recursive division of the array I chose to keep keep track of the middle index of every three numbers. Using the index of the middle number,...
• 43
1 vote
67 views

### Why is my function timing out when run with a larger data set?

I am working on a Code Kata ...
• 163
1 vote
314 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
118 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. ...
• 109
1 vote
2k 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
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 ...