Questions tagged [data-structure]
For questions about mathematical background of data structures, including analysis and proofs and for questions based on some data structure properties. Data structures aim to allow efficient processing of particular queries on the data they contain.
143
questions
0
votes
2
answers
64
views
$T(n) = 3T(\frac{n}{3}) + n\log{n}$ How can I solve this recurrence using the iteration method? [closed]
$T(n) = 3T(\frac{n}{3}) + n\log{n}$
How can I solve this recurrence using the iteration method?
If anyone can solve it and show me how that would be really swell.
- 1
1
vote
0
answers
33
views
What are the possible levels of the $k$th largest element in a max-heap of $n$ distinct elements? [CLRS]
I'm interested in solving Exercise 6.1-5 from the fourth edition of CLRS:
At which levels in a max-heap might the $k$th largest element reside for $2 \leq k \leq \lfloor n/2 \rfloor$, assuming that ...
- 24.6k
0
votes
1
answer
38
views
Algorithm for finding maximum of a binary search tree
To find the maximum of a BST I thought that it would be sufficient to start at the root node and then check if it has a right child (The left child is not relevant since every left subtree of a node ...
- 65
0
votes
0
answers
13
views
Why I get the eigen value as $0$ for the minimum variance?
enter image description here
like equation (8.8) for $M_{ii}^B = <B_i B_i> - <B_i><B_i>$ is coming $0$ for my time series data set. But this eigen value should not be $0$ as ...
- 37
1
vote
0
answers
15
views
How to mathematically prove the "transitive property of nested predictors"?
Note: I posted this question on the Stats.Stackexchange site a week ago, but I think it might be better here. It's about proving a theorem I came up with about experiment data set structures, ...
- 111
0
votes
0
answers
18
views
Based on the Zipf's law or a Zipfian distributed data, how to find a "high frequency" or "low frequency" cutoffs?
For example, I have a corpus data set with frequency counts of transitions between one syllable or token predicting the other, and this frequency distribution follows the Zipfian distribution:
...
- 1
1
vote
1
answer
48
views
How to talk about any objects mathematically? (In this case binary trees)
For context I was doing the following exercise in Isabelle theorem prover tutorial:
Let datatype 'a tree = Tip "'a tree" 'a "'a tree"
Define a ...
0
votes
1
answer
40
views
Using Big Oh to prove $f(n)+k$ is $O(g(n))$
Let $f(n)$ and $g(n)$ be positive functions such that $f(n)$ is $O(g(n))$ and $g(n) \ge 1$ for all
$n \ge 1$. Using the definition of “big Oh” show that $f(n) + k$ is $O(g(n))$, where $k > 0$ is ...
1
vote
1
answer
150
views
Prove or disprove big-O asymptotic notation
1.Let $f_1(n),f_2(n)...f_n(n)...$be an infinite series of functions. $f_i(n)$ belongs to $O(n)$ for all $i$. Let $g(k)= \sum_{j=1}^kf_j(j)$ (i.e. $g(1)=f_1(1),g(2)=f_1(1)+f_2(2)$) then $g(n)$ belongs ...
- 11
0
votes
0
answers
110
views
Traversing a binary-tree (heap) data structure (Iteration over pointers to nodes)
I am currently working with heaps and figuring out the details of how they work in a more implementation specific way - still, fairly theoretical/conceptual, without going into the intricacies of (...
- 342
0
votes
0
answers
26
views
References for mathematical structures/spaces on sets of "words" or "sentences" from a semantics pespective?
With today's hype about large language models, I was wondering if there is any research about mathematical structures for describing sets of words or sentences from a "semantics perspective"....
- 861
0
votes
0
answers
34
views
Resources for modelling data structures with set notation
I am working on my thesis and have a software program defined in terms of data structures, i.e. nested structs with fields and methods etc. I would like to ...
- 123
0
votes
1
answer
19
views
Generalized range check for cyclic array (using modulo)
I'm currently dealing with cyclic arrays in Algorithms & Data Structures and wanted to find a "clean" way using the modulo function to express whether an index is within a certain range ...
- 342
0
votes
1
answer
116
views
Amortized analysis insert operation on linked list required in O(1) amortized
Having the following operation that should be implemented using sorted linked list:
Insert(x): insert element x to the data structure and delete all keys smaller than x. (x is a real number)
the ...
- 11
1
vote
0
answers
84
views
Deriving time complexity of Union-Find using only path compression
For the Union-Find algorithm, I've read that using path compression alone gives a worst-case running time of $O(n+f\cdot(1+\log_{2+\frac{f}{n}}(n)))$ for a sequence of $n$ MakeSet operations (and ...
- 53