Linked Questions

4
votes
2answers
456 views

Why isn't an edge-map graph implementation used in practice?

Wikipedia states that three different graph implementations that are used in practice: Adjacency Lists Adjacency Matrix Incidence Matrix While I was learning about these structures, another ...
10
votes
2answers
234 views

Determining the particular number in $O(n)$ time and space (worst case)

$\newcommand\ldotd{\mathinner{..}}$Given that $A[1\ldotd n]$ are integers such that $0\le A[k]\le m$ for all $1\le k\le n$, and the occurrence of each number except a particular number in $A[1\ldotd n]...
3
votes
1answer
366 views

Does my simple, static hash table have O(1) worst case lookup?

Will the following simple hash table construction algorithm be able to construct a static hash table in $O(n)$ expected time, and will the worst case access time be $O(1)$? If not, what are the ...
10
votes
0answers
244 views

Is there a data-structure which is more efficient than both arrays and linked lists? [duplicate]

Background: In this question we care only about worst-case running-time. Array and (doubly) linked lists can be used to keep a list of items and implement the vector abstract data type. Consider the ...
3
votes
0answers
378 views

Data Structure for storing the Sweep Line Status in Sweep Line Algorithms

I have been looking into the sweep line algorithms of finding intersection of line segments and polygon partitioning using monotone polygons. The algorithms require a dynamically balanced binary tree ...
0
votes
0answers
117 views

is hash table a magic?

I have no cs background (algorithm and data structure), but need to find a data analysis related job since my major is math / statistics. However, (I am trying to avoid software engineering related ...
0
votes
2answers
33 views

How does a hash table not require all the keys to be looked through to find a value, i.e. O(N)?

Before starting, I want to say that I understand time complexity, and I understand how a hash table is considered O(1) vs an array having a time comp. of O(N) in terms of what you learn. What I don't ...

15 30 50 per page
1
2