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
4 votes
0 answers
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 ...
user875234's user avatar
4 votes
1 answer
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 ...
Alex Lopatin's user avatar
3 votes
0 answers
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 ...
slepic's user avatar
  • 5,387
3 votes
0 answers
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, ...
Madfish's user avatar
  • 31
3 votes
0 answers
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 ...
Ahmed Karaman's user avatar
3 votes
0 answers
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 ...
Sukhmeet Singh's user avatar
2 votes
0 answers
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 ...
Mircea's user avatar
  • 322
2 votes
0 answers
186 views

2D Array Word Search: Complexity and Optimization

🧩 Objective Determine whether a given word is contained in a 2D Array word search. 🔎 Question 1. What are the time and space complexities of the current algorithm? Time complexity Linear: \$O(2(r * ...
AdamHurwitz's user avatar
2 votes
0 answers
48 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 ...
Dawn17's user avatar
  • 215
2 votes
0 answers
906 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 ...
Kris's user avatar
  • 199
2 votes
0 answers
216 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 ...
Rick's user avatar
  • 121
2 votes
0 answers
48 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 ...
Rick's user avatar
  • 586
2 votes
0 answers
46 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 ...
avghdev's user avatar
  • 135
2 votes
0 answers
94 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 ...
Teddy's user avatar
  • 131
2 votes
0 answers
2k 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 (...
plethora's user avatar
2 votes
0 answers
252 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 ...
Mona Jalal's user avatar
2 votes
0 answers
65 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 (...
Reed G. Law's user avatar
2 votes
0 answers
46 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 ...
Luke's user avatar
  • 181
1 vote
0 answers
23 views

Designing a font definition with multiple variants per glyph

My project penhand tries to visualize the process of writing with a pen. Part of the project is an engine that converts text entry into a sequence of glyphs that are then rendered as animation into a ...
ccprog's user avatar
  • 151
1 vote
0 answers
73 views

Traveling salesman (Dynamic Approach) retrieve path without losing on time complexity

It is difficult to find resources on above programming problem therefore I've decided to ask a question on this forum. Using memoization and dynamic programming we can obtain a code that gives \$O(2^N ...
Kacper's user avatar
  • 11
1 vote
0 answers
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,...
EL_H4CK0's user avatar
1 vote
0 answers
67 views

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

I am working on a Code Kata ...
MicFin's user avatar
  • 163
1 vote
0 answers
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(\...
Elya Livshitz's user avatar
1 vote
0 answers
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. ...
neet's user avatar
  • 109
1 vote
0 answers
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 ...
Aarish Ramesh's user avatar
1 vote
0 answers
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 ...
Meena Chaudhary's user avatar
0 votes
0 answers
173 views

Program to generate a tree of permutations

There is a computation I'm doing with permutations (permutations of varying length of an entire interval [1,N] for some N) in python that I feel could be faster. ...
Matt Samuel's user avatar
0 votes
0 answers
64 views

Calculate maximum value of expression for potential associations

I have an algorithm that calculates the maximum value of an expression that is made from numbers and * or + by adding parentheses. It has 3 nested loops, so the time complexity should be N^3 ...
Tomas's user avatar
  • 1