I would like to store an input of tab separated values where say C1, C2, C3 and C4 represent the columns of the data and there are N rows of data. If so, I could do lookups in the hash to see if some given values for C1,C2,C3,C4 exist. Someone suggested to me that, in the worst case, the space complexity of this was N4. I would like help formulating a clear explanation as to why that is not true.
space complexity of multi-dimensional hash
375 Views Asked by harschware At
1
There are 1 best solutions below
Related Questions in HASH
- Trouble validating md5 hashed password with randomly generated salt?
- Why k and l for LSH used for approximate nearest neighbours?
- PHP password_hash() / bcrypt
- Unique hash/index for time interval
- Order-independent Hash Algorithm
- git hard reset - what am I doing wrong?
- Java HashMap, hashCode() equals() - how to be consistent with multiple keys?
- Create hash from variables in loop
- Hashing integer coordinates of different sizes
- Xcode salting and hashing a password
- Is there a way to generate a Guid from a list of Guids?
- Path reconstruction with Hashing?
- Creating a Hash with keys from an array and empty arrays as the values
- How to read data from a different file without using YAML or JSON
- change value in hash using an array of keys in ruby
Related Questions in HASHTABLE
- Borrow mutable and immutable reference in the same block
- Loss of an element from hashtable using JDI
- csv parsing and manipulation using python
- java - how to create custom hashtable iterator?
- How to convert a string to a key for hash table
- How to use hash tables when amount of slots is unknown?
- Access a value in a generic array inside a generic class
- Why not use hash table with overflow area?
- Please share some insights on rehash method in java?
- Removing a node from a LinkedList (C#)
- Is there an extensible open address hash table?
- Valgrind newbie, can't seem to make it happy
- Are the "key" and "value" terms for hash tables and associative arrays used interchangeably?
- Why is the cost of a hash lookup O(1) when evaluating the hash function might take more time than that?
- How does hopscotch hashing actually work?
Related Questions in BIG-O
- Big-O insert for 2 dimensional array
- Compare growth of function
- Time complexity of nested for loops
- TIme complexity of various nested for loops
- Time complexity analysis for finding the maximum element
- Calculating the Recurrence Relation T(n)=T(n / log n) + Θ(1)
- Why is the cost of a hash lookup O(1) when evaluating the hash function might take more time than that?
- How can I tell how many times these nested statements will execute?
- Update minimum spanning tree if edge is added
- Have I properly sorted these runtimes in order of growth?
- find the complexity for loop
- Specific behaviour of {if else} in C
- What is the time complexity of the below function?
- Would this function be O(n^2log_2(n))?
- Complexity of a nested geometric sequence
Related Questions in MULTIDIMENSIONAL-ARRAY
- How to sort a multi-dimensional array by the second array in descending order?
- C programming: Create and write 2D array of files as function
- Working with multiple array in PHP
- PHP multidimensional array, average of duplicate values
- Multiple parameters in a Dictionary
- navigate through multidimensional PHP array by relative path
- How to double values in 2d array? C++
- Multidimensional Array view defined line
- .NET Array with Multiple Data Types
- Multidimensional Array modify values
- Rearrange multidimensional array from other array
- Callback set_message not working with multidimensional array post
- Javascript push multidimensional array only checked checkboxes
- Program crash while trying to print a bidimensional array
- How to extract all 2nd level values (leaf nodes) from a 2-dimensional array and join with commas?
Related Questions in SPACE-COMPLEXITY
- How to Compute Space Complexity for Printing All paths which Sum to a Given Value in Binary Tree
- The call stack size of quick sort
- How to Compute Space Complexity for Binary SubTree Finding
- Solitaire: storing guaranteed wins cheaply
- How to compare the complexity of two methods in Java?
- toString time and space complexity
- calculate time/space complexity while running program
- Bellman-Ford Algorithm Space Complexity
- Space complexity in memoized fibonacci code
- Capital Movement | Competitive Programming
- Complexity characteristics of a simple heap-based array function
- The most time/space efficient way to list all indices in an object
- Best data structure for closest range
- Space complexity of a function which builds n-sized array after calling it
- Heap Sort Space Complexity
Trending Questions
- UIImageView Frame Doesn't Reflect Constraints
- Is it possible to use adb commands to click on a view by finding its ID?
- How to create a new web character symbol recognizable by html/javascript?
- Why isn't my CSS3 animation smooth in Google Chrome (but very smooth on other browsers)?
- Heap Gives Page Fault
- Connect ffmpeg to Visual Studio 2008
- Both Object- and ValueAnimator jumps when Duration is set above API LvL 24
- How to avoid default initialization of objects in std::vector?
- second argument of the command line arguments in a format other than char** argv or char* argv[]
- How to improve efficiency of algorithm which generates next lexicographic permutation?
- Navigating to the another actvity app getting crash in android
- How to read the particular message format in android and store in sqlite database?
- Resetting inventory status after order is cancelled
- Efficiently compute powers of X in SSE/AVX
- Insert into an external database using ajax and php : POST 500 (Internal Server Error)
Popular Questions
- How do I undo the most recent local commits in Git?
- How can I remove a specific item from an array in JavaScript?
- How do I delete a Git branch locally and remotely?
- Find all files containing a specific text (string) on Linux?
- How do I revert a Git repository to a previous commit?
- How do I create an HTML button that acts like a link?
- How do I check out a remote Git branch?
- How do I force "git pull" to overwrite local files?
- How do I list all files of a directory?
- How to check whether a string contains a substring in JavaScript?
- How do I redirect to another webpage?
- How can I iterate over rows in a Pandas DataFrame?
- How do I convert a String to an int in Java?
- Does Python have a string 'contains' substring method?
- How do I check if a string contains a specific word?
The other person is thinking that if you try to store an N by N grid of points, there will be N4 points to store.
But if you have N points, then you're just storing a hash. And a hash with N data points typically takes O(N) space. (Technically it takes the size of the hash table plus the space for the data, but people usually dynamically size the hash table to be the same order of magnitude size as the data set.)