{
  "$type": "site.standard.document",
  "description": "Rope implementation in harelang.",
  "path": "/posts/hare-rope/",
  "publishedAt": "2024-05-28T01:10:02.000Z",
  "site": "at://did:plc:6n2ngs7zpcpwxz3jaoxj56tu/site.standard.publication/3mo6y7ludvn2h",
  "tags": [
    "programming",
    "math"
  ],
  "textContent": "A Rope is a data structure that manages an ordered set of characters. Just like\na string!\n\nYou can read more about it on its Wikipedia article.)\n\nSome of the key Big-O differences are the following:\n| Operation | Rope | String |\n| --- | --- | --- |\n| Index | O(log n) | O(1) |\n| Split | O(log n) | O(1) |\n| Concatenate | O(1) amort., O(log n) worst | O(n) |\n| Iterate over each character | O(n) | O(n) |\n| Insert | O(log n) | O(n) |\n| Append | O(1) amort., O(log n) worst | O(1) amort., O(n) worst |\n| Delete | O(log n) | O(n) |\n| Report | O(j + log n) | O(j) |\n| Build | O(n) | O(n) |\n\nTable taken from Comparison with monolithic arrays#Comparison_with_monolithic_arrays)",
  "title": "Hare Rope"
}