Relevant bibliographies by topics / Amortized complexity

Contents

  1. Journal articles
  2. Books
  3. Book chapters
  4. Conference papers

Academic literature on the topic 'Amortized complexity'

Author: Grafiati
Published: 28 June 2021
Last updated: 11 February 2022

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Amortized complexity.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Amortized complexity"

1

Tarjan, Robert Endre. "Amortized Computational Complexity." SIAM Journal on Algebraic Discrete Methods 6, no. 2 (April 1985): 306–18. http://dx.doi.org/10.1137/0606031.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Feder, Tomás, Eyal Kushilevitz, Moni Naor, and Noam Nisan. "Amortized Communication Complexity." SIAM Journal on Computing 24, no. 4 (August 1995): 736–50. http://dx.doi.org/10.1137/s0097539792235864.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Nipkow, Tobias, and Hauke Brinkop. "Amortized Complexity Verified." Journal of Automated Reasoning 62, no. 3 (March 13, 2018): 367–91. http://dx.doi.org/10.1007/s10817-018-9459-3.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Kingston, Jeffrey H. "The amortized complexity of Henriksen's algorithm." BIT 26, no. 2 (June 1986): 156–63. http://dx.doi.org/10.1007/bf01933741.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Bahendwar, Isha Ashish, Ruchit Purshottam Bhardwaj, and Prof S. G. Mundada. "Amortized Complexity Analysis for Red-Black Trees and Splay Trees." International Journal of Innovative Research in Computer Science & Technology 6, no. 6 (November 2018): 121–28. http://dx.doi.org/10.21276/ijircst.2018.6.6.2.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Cramer, Ronald, Ivan Damgård, and Marcel Keller. "On the Amortized Complexity of Zero-Knowledge Protocols." Journal of Cryptology 27, no. 2 (January 31, 2013): 284–316. http://dx.doi.org/10.1007/s00145-013-9145-x.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

NAVARRO, GONZALO, RODRIGO PAREDES, PATRICIO V. POBLETE, and PETER SANDERS. "STRONGER QUICKHEAPS." International Journal of Foundations of Computer Science 22, no. 04 (June 2011): 945–69. http://dx.doi.org/10.1142/s0129054111008507.

Full text
Abstract:
The Quickheap (QH) is a recent data structure for implementing priority queues which has proved to be simple and efficient in practice. It has also been shown to offer logarithmic expected amortized complexity for all of its operations. Yet, this complexity holds only when keys inserted and deleted are uniformly distributed over the current set of keys. This assumption is in many cases difficult to verify, and does not hold in some important applications such as implementing some minimum spanning tree algorithms using priority queues. In this paper we introduce an elegant model called a Leftmost Skeleton Tree (LST) that reveals the connection between QHs and randomized binary search trees, and allows us to define Randomized QHs. We prove that these offer logarithmic expected amortized complexity for all operations regardless of the input distribution. We also use LSTs in connection to α-balanced trees to achieve a practical α-Balanced QH that offers worst-case amortized logarithmic time bounds for all the operations. Both variants are much more robust than the original QHs. We show experimentally that randomized QHs behave almost as efficiently as QHs on random inputs, and that they retain their good performance on inputs where that of QHs degrades.
APA, Harvard, Vancouver, ISO, and other styles
8

Hiary, Ghaith A. "An amortized-complexity method to compute the Riemann zeta function." Mathematics of Computation 80, no. 275 (January 25, 2011): 1785–96. http://dx.doi.org/10.1090/s0025-5718-2011-02452-x.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Hoogerwoord, Rob R. "Functional Pearls A symmetric set of efficient list operations." Journal of Functional Programming 2, no. 4 (October 1992): 505–13. http://dx.doi.org/10.1017/s0956796800000526.

Full text
Abstract:
In this paper we show that it is possible to implement a symmetric set of finite-list operations efficiently; the set is symmetric in the sense that lists can be manipulated at either end. We derive the definitions of these operations from their specifications by calculation. The operations have O(1) time complexity, provided that we content ourselves with, so-called, amortized efficiency, instead of worst-case efficiency
APA, Harvard, Vancouver, ISO, and other styles
10

Dumitrescu, Adrian. "A Selectable Sloppy Heap." Algorithms 12, no. 3 (March 6, 2019): 58. http://dx.doi.org/10.3390/a12030058.

Full text
Abstract:
We study the selection problem, namely that of computing the ith order statistic of n given elements. Here we offer a data structure called selectable sloppy heap that handles a dynamic version in which upon request (i) a new element is inserted or (ii) an element of a prescribed quantile group is deleted from the data structure. Each operation is executed in constant time—and is thus independent of n (the number of elements stored in the data structure)—provided that the number of quantile groups is fixed. This is the first result of this kind accommodating both insertion and deletion in constant time. As such, our data structure outperforms the soft heap data structure of Chazelle (which only offers constant amortized complexity for a fixed error rate 0 < ε ≤ 1 / 2 ) in applications such as dynamic percentile maintenance. The design demonstrates how slowing down a certain computation can speed up the data structure. The method described here is likely to have further impact in the field of data structure design in extending asymptotic amortized upper bounds to same formula asymptotic worst-case bounds.
APA, Harvard, Vancouver, ISO, and other styles
More sources

Books on the topic "Amortized complexity"

1

Sundar, R. Amortized complexity of data structures. New York: Courant Institute of Mathematical Sciences, New York University, 1991.

Find full text
APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Amortized complexity"

1

Nipkow, Tobias. "Amortized Complexity Verified." In Interactive Theorem Proving, 310–24. Cham: Springer International Publishing, 2015. http://dx.doi.org/10.1007/978-3-319-22102-1_21.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Roland, Jérémie, and Mario Szegedy. "Amortized Communication Complexity of Distributions." In Automata, Languages and Programming, 738–49. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. http://dx.doi.org/10.1007/978-3-642-02927-1_61.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Fiedor, Tomáš, Lukáš Holík, Adam Rogalewicz, Moritz Sinn, Tomáš Vojnar, and Florian Zuleger. "From Shapes to Amortized Complexity." In Lecture Notes in Computer Science, 205–25. Cham: Springer International Publishing, 2017. http://dx.doi.org/10.1007/978-3-319-73721-8_10.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Nikishkin, Vladimir. "Amortized Communication Complexity of an Equality Predicate." In Computer Science – Theory and Applications, 212–23. Berlin, Heidelberg: Springer Berlin Heidelberg, 2013. http://dx.doi.org/10.1007/978-3-642-38536-0_19.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Cascudo, Ignacio, Ronald Cramer, Chaoping Xing, and Chen Yuan. "Amortized Complexity of Information-Theoretically Secure MPC Revisited." In Lecture Notes in Computer Science, 395–426. Cham: Springer International Publishing, 2018. http://dx.doi.org/10.1007/978-3-319-96878-0_14.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Soisalon-Soininen, Eljas, and Peter Widmayer. "Amortized Complexity of Bulk Updates in AVL-Trees." In Algorithm Theory — SWAT 2002, 439–48. Berlin, Heidelberg: Springer Berlin Heidelberg, 2002. http://dx.doi.org/10.1007/3-540-45471-3_45.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Cramer, Ronald, and Ivan Damgård. "On the Amortized Complexity of Zero-Knowledge Protocols." In Advances in Cryptology - CRYPTO 2009, 177–91. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. http://dx.doi.org/10.1007/978-3-642-03356-8_11.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Golowich, Noah, and Madhu Sudan. "Round Complexity of Common Randomness Generation: The Amortized Setting." In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1076–95. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2020. http://dx.doi.org/10.1137/1.9781611975994.66.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Cramer, Ronald, Ivan Damgård, and Valerio Pastro. "On the Amortized Complexity of Zero Knowledge Protocols for Multiplicative Relations." In Lecture Notes in Computer Science, 62–79. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012. http://dx.doi.org/10.1007/978-3-642-32284-6_4.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Cramer, Ronald, Ivan Damgård, Chaoping Xing, and Chen Yuan. "Amortized Complexity of Zero-Knowledge Proofs Revisited: Achieving Linear Soundness Slack." In Lecture Notes in Computer Science, 479–500. Cham: Springer International Publishing, 2017. http://dx.doi.org/10.1007/978-3-319-56620-7_17.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Amortized complexity"

1

Baig, Mirza Ahad, Danny Hendler, Alessia Milani, and Corentin Travers. "Long-Lived Snapshots with Polylogarithmic Amortized Step Complexity." In PODC '20: ACM Symposium on Principles of Distributed Computing. New York, NY, USA: ACM, 2020. http://dx.doi.org/10.1145/3382734.3406005.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Ellen, Faith, Panagiota Fatourou, Joanna Helga, and Eric Ruppert. "The amortized complexity of non-blocking binary search trees." In the 2014 ACM symposium. New York, New York, USA: ACM Press, 2014. http://dx.doi.org/10.1145/2611462.2611486.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Samorodnitsky, Alex, and Luca Trevisan. "A PCP characterization of NP with optimal amortized query complexity." In the thirty-second annual ACM symposium. New York, New York, USA: ACM Press, 2000. http://dx.doi.org/10.1145/335305.335329.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Giakkoupis, George, and Philipp Woelfel. "Randomized Mutual Exclusion with Constant Amortized RMR Complexity on the DSM." In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2014. http://dx.doi.org/10.1109/focs.2014.60.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Chan, David Yu Cheng, and Philipp Woelfel. "Recoverable Mutual Exclusion with Constant Amortized RMR Complexity from Standard Primitives." In PODC '20: ACM Symposium on Principles of Distributed Computing. New York, NY, USA: ACM, 2020. http://dx.doi.org/10.1145/3382734.3405736.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Giakkoupis, George, and Philipp Woelfel. "Randomized Abortable Mutual Exclusion with Constant Amortized RMR Complexity on the CC Model." In PODC '17: ACM Symposium on Principles of Distributed Computing. New York, NY, USA: ACM, 2017. http://dx.doi.org/10.1145/3087801.3087837.

Full text
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Amortized complexity' for particular source types:
Journal articles
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography