Linked Questions

38
votes
3answers
4k views

How is algorithm complexity modeled for functional languages?

Algorithm complexity is designed to be independent of lower level details but it is based on an imperative model, e.g. array access and modifying a node in a tree take O(1) time. This is not the case ...
11
votes
2answers
2k views

Array-like immutable (persistent) data structure implementation with fast indexing, append, prepend, iteration

I'm looking for a persistent data structure similar to array (but immutable), allowing for fast indexing, append, prepend, and iteration (good locality) operations. Clojure provides persistent Vector,...
1
vote
1answer
379 views

Why are functional programs considered slower than procedural counterparts asymptotically, if the opposite appears true?

I've read and been told way too many times that functional algorithms and data structures have an obligatory O(log(N)) slowdown in respect to their procedural (for-...
3
votes
1answer
177 views

rope data structure - undo operation

I was reading (wikipedia) about how the rope data structure might be suitable for a text editor. Within the article it mentions "If only nondestructive versions of operations are used, rope is a ...
0
votes
0answers
414 views

How to find point of maximum overlap in both X and Y Axis?

I was given a array R of n rectangles [each element in the array is a bottom left point(x1,y1) and a top right point (x2,y2)] , parallel to the axis, and an array P of n points [each element is a ...
4
votes
2answers
67 views

Calculate $(u,v) \in \mathbb{R}$ so that $\sum (a_i + b_i)$ with $ a_i \geq u$ and $b_i \geq v$ maximizes

I have two datasets $A$ and $B$: $A = \{1, 5, -34, 34.34323, -23.5444, 9.43, ....\}$ $B = \{-0.5, 44, -0.243, -3455, 2.22221, -23.23, ....\}$ Those datasets contain a big amount of "random" numbers (...
2
votes
0answers
371 views

How would a priority queue be implemented in a functional programming language?

How would a priority queue be coded efficiently in a functional programming language? I'm new to functional programming, but I'm having difficulty understanding how a data structure that seems to ...
3
votes
2answers
170 views

Skip List estimate number of elements less than (or greater than) a value

I am looking for a thread safe data structure where an element can be searched in $O(\log n)$, for any value, $x$, the number of elements greater than (or less than) can be estimated in $O(\log n)$,...
2
votes
1answer
96 views

Can we implement every algorithm using only immutable variables?

Can we implement every algorithm using only immutable variables such that their space and time complexity is the same as using mutable variables?
2
votes
2answers
67 views

Is purely functional programming in some situations less efficient than imperative programming?

I am used to implementing algorithms in imperative languages. Many of the algorithms I have implemented use hash maps, hash sets, mutable arrays, heaps, doubly linked lists, etc. I understand that ...
3
votes
1answer
56 views

Lower complexity bounds without mutation

Lower complexity bounds tend to be a very hard problem in general. Despite this, I was wondering if there are any theoretical results that relate lower complexity bounds for some class of problems in ...
1
vote
1answer
35 views

Improving copy cost of a bit array by using big-endian Patricia Trees (or similar)

I have an algorithm that on each iteration generates a copy of an object containing a bit array and modifies it (the modification is limited to just 1 element per copy) While doing the time analysis ...