A simple implementation of the packed memory array
Switch branches/tags
Nothing to show
Pull request Compare This branch is 1 commit behind reddragon:master.
Latest commit 47173e0 May 19, 2012 @dhruvbird cosmetic changes
Permalink
Failed to load latest commit information.
doc cosmetic changes May 19, 2012
include
pma_tests Changed perms to non executable May 3, 2012
tests Fixed warnings in Implementation 1 Apr 29, 2012
Makefile
README.md
impl1.cpp Changed perms to non executable May 3, 2012
impl2.cpp Changed perms to non executable May 3, 2012

README.md

Benchmarks

Implementation-1

Time to insert 107 elements: 3min 8sec*

Implementation-2

Time to insert 107 elements: 2min 40sec*

* (When compiled with -O2 using g++, on a 1.73 GHz Pentium M machine)

Analysis

  • Complexity of an insert: O(log2n) (amortized)

  • Complexity of find (binary search): O(log2n) (worst-case)