Academia.eduAcademia.edu
All Topics
Computer Science
Algorithms and Data Structures
Algorithm Complexity

Algorithm Complexity

description24 papers
group3 followers
lightbulbAbout this topic
Algorithm complexity refers to the quantitative measure of the resources required by an algorithm to solve a problem, typically expressed in terms of time (time complexity) and space (space complexity) as a function of the input size. It provides insights into the efficiency and scalability of algorithms.
lightbulbAbout this topic
Algorithm complexity refers to the quantitative measure of the resources required by an algorithm to solve a problem, typically expressed in terms of time (time complexity) and space (space complexity) as a function of the input size. It provides insights into the efficiency and scalability of algorithms.

Key research themes

1. How can formal methods verify time complexity properties of classical algorithms?

This research area explores the use of formal verification tools and specification languages to rigorously prove both functional correctness and explicit complexity bounds (such as worst-case time complexity) of well-known classical algorithms. The motivation lies in moving beyond informal or pen-and-paper proofs to automated, machine-checked guarantees suitable for educational purposes and higher assurance in software systems.

Verifying Time Complexity of Binary Search using Dafny
by Shmuel S Tyszberowicz

2022, ArXiv

Key finding: The authors successfully specified and formally proved in Dafny the worst-case time complexity of binary search to belong to O(log n), alongside functional correctness. Their methodology involved introducing a formal... Read more
articleView PaperdownloadDownload
keyboard_arrow_downShow more

2. What are effective empirical and statistical methods to analyze the computational complexity of algorithms in practical scenarios?

This thread investigates approaches that combine experimental timing measurements with statistical modeling (e.g., regression analysis) to derive empirical complexity characterizations of algorithms. By doing so, it provides a practical complement to classical asymptotic complexity theory, especially relevant for complex or cryptographic algorithms where theoretical analysis is hard and runtime behavior is critical.

Empirical and Statistical Complexity Analysis of AES-128
by Dr. Soubhik Chakraborty

2024, Research Square (Research Square)

Key finding: The authors empirically measured the runtime of AES-128 encryption with varying input sizes and performed regression-based statistical analysis to fit the observed timings to asymptotic complexity models. They established a... Read more
articleView PaperdownloadDownload
keyboard_arrow_downShow more

3. How do algorithmic analysis methods account for realistic costs of operations such as symbol comparisons in sorting/searching algorithms?

This theme focuses on extending algorithm complexity analysis to incorporate realistic cost measures reflecting actual operation costs—particularly the cost of symbol-by-symbol comparisons rather than abstract key comparisons. By modeling keys as words generated by probabilistic sources and analyzing symbol-level operations, this approach bridges theoretical analysis with practical performance evaluation of sorting and searching algorithms.

A general framework for the realistic analysis of sorting and searching algorithms. Application to some popular algorithms
by Brigitte Vallée

2025

Key finding: The authors devised a general analytical framework based on the probabilistic modeling of sources generating keys to estimate average-case complexity in terms of symbol comparisons instead of traditional key comparisons.... Read more
articleView PaperdownloadDownload
keyboard_arrow_downShow more

4. What insights emerge from complexity considerations in human and quantum computation, especially in error resilience and group decision-making?

This interdisciplinary theme studies how computational complexity concepts (e.g., NP-completeness, PSPACE-completeness) inform the ability of human groups to verify solutions and the robustness of quantum algorithms to noise. It integrates complexity theory with cognitive science and quantum information to understand practical limitations and efficiencies.

On the Verification Complexity of Group Decision-Making Tasks
by Ofra Amir

2023, Proceedings of the AAAI Conference on Human Computation and Crowdsourcing

Key finding: The study empirically showed that human groups have greater ability to recognize correct solutions to problems from easy-to-verify complexity classes (NP-Complete) compared to hard-to-verify classes (PSPACE-Complete),... Read more
articleView PaperdownloadDownload
Noise effects in the quantum search algorithm from the viewpoint of computational complexity
by Jerzy Klamka

2025, International Journal of Applied Mathematics and Computer Science

Key finding: The authors analyzed Grover’s quantum search algorithm under the influence of quantum noise modeled by completely positive trace-preserving maps and determined thresholds on noise levels below which the quantum advantage over... Read more
articleView PaperdownloadDownload
keyboard_arrow_downShow more

5. How can polynomial methods from circuit complexity guide algorithmic design and complexity lower bounds?

This emerging approach applies polynomial representations of Boolean functions—originally developed for circuit lower bounds—to design efficient algorithms, linking algebraic structure to computational complexity. The polynomial method transforms circuit complexity insights into concrete algorithmic tools, showing new pathways to both lower bounds and constructive algorithms.

The Polynomial Method in Circuit Complexity Applied to Algorithm Design (Invited Talk)
by Ryan Williams

2023

Key finding: The paper surveys how representing circuits by low-complexity polynomials enables proving impossibility (lower bounds) results but, more recently, has also informed the design of faster algorithms for fundamental... Read more
articleView PaperdownloadDownload
keyboard_arrow_downShow more

Related Topics

  • Cryptography
  • Information Security
  • Human Computer Interaction
  • Machine Learning

    • All papers in Algorithm Complexity

    Noise effects in the quantum search algorithm from the viewpoint of computational complexity
    by Jerzy Klamka

    2025, International Journal of Applied Mathematics and Computer Science

    We analyse the resilience of the quantum search algorithm in the presence of quantum noise modelled as trace preserving completely positive maps. We study the influence of noise on the computational complexity of the quantum search... more
    descriptionView Paperarrow_downwardDownload
    Two New Algorithms for Line Clipping in E2 and Their Comparison
    by DUC QUANG BUI

    2023, arXiv (Cornell University)

    New efficient algorithms for the line clipping by the given rectangle in E 2 are presented. The first algorithm is based on the line direction evaluation, the second one is based on a new coding technique of clipping rectangle's vertices.... more
    descriptionView Paperarrow_downwardDownload
    Aplikácia Teórie Grafov V Leteckej Doprave
    by Jan Zýka

    2023, Perner's Contacts

    Práca ja zameraná na aplikácie teórie grafov do leteckej dopravy – aké sú možnosti využitia a aplikácie grafov v leteckej doprave. Zaoberá sa analýzou, skúmaním a následne  riešením aplikácie teórie grafov do leteckej dopravy pri... more
    descriptionView Paperarrow_downwardDownload
    A Comparison of O (1) and Cyrus-Beck Line Clipping Algorithms in E 2 and E 3
    by 4B SUP

    2022

    A comparison of a new algorithm for line clipping in E 2 and E 3 by convex polygon and/or polyhedron with O(1) processing complexity and Cyrus-Beck algorithm is presented. The new algorithm in E 2 is based on dual space representation and... more
    Fig. 6.1. Semidual representation of convex polyhedron The table show six planes with its numbers. On this number we will reference in algorithm 6.1.
    Fig. 3.1. Number of edges in AEL dependent on subdivision in the direction of q (N = 10, nx is 1, 10, 100 and 1000) rMAy ours These conditions guarantee that each list of AEL contains up to three edges. It is necessary to point out that these conditions can extremely increase subdivisions of semidual spaces and memory requirements can be above system possibilities. That is why these conditions cannot be realized. Then it is essential to find an optimal level of subdivision which subdivide the semidual spaces sufficiently, but on the other hand which do not exceed above available memory. Experimental results of space subdivision for a polygon with N = 10 are presented in Fig. 3.1.,Fig. 3.2.
    lable 5.4. Processing times for different number of clipped line Polygon with N = 10, coefficients of O(1) : n.=10, ng=50 Dependence of a processing time of O(1) algorithm on a probability that clipped lines intersect the given polygon for N=10 is shown in Table 5.4 and Fig. 5.2. Experimental results show that O(1) algorithm is faster than CB algorithm if number of clipped lines is greater than 5000. The limit value is the same for all probabilities of intersection of a polygon by clipped line.
    The processing time of the proposed O(1) algorithm depends on a probability of intersection of the given polygon. It is also presented in Table 5.5 and Fig. 5.3. The time complexity of the CB algorithm is nearly constant, but the more clipped lines intersect the polygon, the more processing time is needed in O(1) algorithm. It is due to the test whether a line intersects a polygon is faster for a line does not intersecting the given polygon than for a line which intersects it.
    Table 2.1. Representation of geometrical primitives
    Fig. 3.2. Number of edges in AEL dependent on subdivision in the direction of k (N = 10, ng is 1, 10, 100 and 1000)
    Table 5.1. Experimental results of processing times (M=10.000, Pr=0%, coefficients of O(1): n.=10, ng=50) Fig. 5.1. Experimental results of processing time are presented in Table 5.1, Table 5.2 and 5.1. Experimental results of processing time are presented in Table 5.1, Table 5.2 and 5. Experimental results of O(1) algorithm and comparison with CB algorithm in FE’
    Fig. 5.2. Processing times for different number of clipped lines
    Fig. 5.3. Processing times for different probability of intersection Table 5.5. Processing times for different probability of intersection N = 10, M = 10.000, coefficients of O(1) : n.=10, ng=50
    Table 3.1. Preprocessing time of AEL (subdivision in the direction of k : nx = 10)
    The first test is determining the speed of the algorithm with a various number of the polygon facets in dependence on subdivision of dual space. In table and in some graphs there adequate results of CB algorithm are presented . For even type of subdivision of dual space three graphs are presented. Preprocessing graph, processing graph and sum of preprocessing and processing consuming time graph. Very interesting is the third graph. This graph shows an optimal subdivision of the dual space. The shown optimum is relative. It is optimum for sum of preprocessing and processing time, but in some applications we want to minimize the time of processing. For this application type, the presented optimum is improper. Tables and graphs are included in appendix. The tests are computed for ny=n,, nx=2,
    The construction time of AEL is presented in Table 3.1. and Fig. 3.3
    Table 5.3. Theoretical and experimental efficiencies A comparison of theoretical estimations and experimental results is presented in Table 5.3.
    descriptionView Paperarrow_downwardDownload
    Use of a simulation model for the development of an automatic algorithm for creating a routing table and path evaluation in a conveyor system
    by Dominika Weyrová

    2022

    The diploma thesis deals with the use of a simulation model for the development of an automatic algorithm for the creation of a routing table and route evaluation in a transport system. It includes a search of modeling and simulation... more
    descriptionView Paperarrow_downwardDownload
    An optimal algorithm for 3D triangle mesh slicing
    by Rodrigo Gregori

    2022, Computer-Aided Design

    This is a PDF file of an unedited manuscript that has been accepted for publication. As a service to our customers we are providing this early version of the manuscript. The manuscript will undergo copyediting, typesetting, and review of... more
    Figure 9: Running times of the three slicing algorithms (Park, Slic3r, Proposed) for uniform slicing (left) and 3—11 and 6-8 million items (triangles, planes, or segments) per second, respectively.
    The worst case cost in terms of n and k is when every triangle intersects every plane. It
    Figure 8: (a) State of the CONTOUR-CONSTRUCTION algorithm after step 12; (b) state just before step 21 The next step in the process would be to identify the sense (clockwise or counterclock-
    possible outcomes, it provides at most 1 bit of information about the input data. Therefor« the number of comparisons must be at least n log, k. We conclude that any algorithm that solves problem P using only comparisons, requires at least Q.(n log k) operations. The sam
    Table 1: STL models used in the experiments, showing the number of triangles (n), the number of planes (A
    Figure 12: Total running time of our algorithm, expressed as percentages, relative to the running times of Park’s Park’s algorithm and of Slic3r, for each of those models. algorithm and of Slic3r, for each of the models of Table | with uniform slicing.
    Figure 7: (a) A set of segments produced by the mesh slicing algorithm for one plane; (b) the hash table buil
    This paper describes optimal algorithms to solve the mesh slicing step (Section 3) and the can consume up to 60% of the entire process planning time [4]. slicing task only as slicing. The slicing process can be divided into four sub-tasks as shown in Figure 1. These steps
    that delimit the interior (i.e. the area with and without material inside the part) of the object Figure 3: Selected steps in the additive layered manufacturing process planning: (a) slicing the triangle mesh, generating a set (b) of line segments on each plane, that are connected into closed loops (c).
    Figure 2: A triangle mesh of the surface of a 3D object model (a) and examples of uniform slicing (b) and icing provides better surface quality in critical features of the printed model while savin; layer thickness (uniform slicing) or with variable layer thickness (adaptive slicing). Adaptive
    Figure 5: An example of triangle grouping by zmin (depicted by black dots) in step 3 of Algorithm 1. The resulting lists are: Ly = {ti}, L2 = { }, 03 = {te,ts,ts,t5},L4 = {te,t7},L5 = { } and Le = {ts}. After step 7 with 1 = 4, the sweeping plane is assumed to lie between P3 and P4, and the active set will be A= {ts, t3, te, t7}. Figure 5: An example of triangle grouping by zmin (depicted by black dots) in step 3 of Algorithm 1. The is used to locate the correct list index 7 for each triangle t (steps 18-23).
    running time in each row, for each type of problem. The Slic3r software is limited to uniform slicing. Figure 10: Samples of STL models (Femur and Soldier) and mesh slicing (layer thickness of 1.0 mm and 2.0
    Table 3: Running times (in seconds) for the four contour-construction algorithms (Trivial, Park, Slic3r, anc
    Figure 11: Running times of the four chaining implementations (Trivial, Park, Slic3r, and Proposed) for the
    As the table shows, our algorithm was faster than the other two for all models, sometimes by a large factor. For example, Slic3r took almost 36 minutes to process the Skull model, Table 4: Total running times (slicing and contour-construction steps), in seconds, for Park’s algorithm, the Slic31
    one or more segments; and a value, that is a pair (v, w) of points such that {u,v} and {u, w}
    descriptionView Paperarrow_downwardDownload
    Hash Function for geometry Reconstruction
    by Vaclav Skala

    2022

    Abstract. There are many applications where data structures use a hash function. The hash data structures are widely used across all fields of computer science. Nevertheless the design or selection of hash function for data sets with... more
    descriptionView Paperarrow_downwardDownload
    Parallel Triangular Mesh Reduction
    by Vaclav Skala

    2022

    The visualization of large and complex models is required frequently. This is followed by number of operations which must be done before visualization itself, whether it is an analysis of input data or a model simplification. One of the... more
    descriptionView Paperarrow_downwardDownload
    Visualization and Spatial Perception
    by Vaclav Skala

    2022

    Generally the expression "visualization" means data processing so that a human being can imagine the physical or other phenomena represented by the given data sets. Although the visual understanding is nearly understood... more
    descriptionView Paperarrow_downwardDownload
    Line Clipping by Convex and Nonconvex Polyhedra in E 3
    by Vaclav Skala

    2022

    A new algorithm for clipping lines against convex polyhedron with O N ( ) complexity is given with modification for nonconvex polyhedron. The suggested algorithm is faster for higher number of facets of the given polyhedron than the... more
    descriptionView Paperarrow_downwardDownload
    Hash Function for Geometry Reconstruction in Rapid Prototyping
    by Vaclav Skala

    2022

    There are many applications where data structures use a hash function. The hash data structures are widely used across all fields of computer science. Nevertheless the design or selection of hash function for data sets with unknown... more
    descriptionView Paperarrow_downwardDownload
    A Comparison of O(1) and Cyrus-Beck Line Clipping Algorithms in E2 and E3
    by Vaclav Skala

    2022

    A comparison of a new algorithm for line clipping in E 2 and E 3 by convex polygon and/or polyhedron with O(1) processing complexity and CyrusBeck algorithm is presented. The new algorithm in E 2 is based on dual space representation and... more
    Table 5.1. Experimental results of processing times (M=10.000, Pr=0%, coefficients of O(1): n.=10, ng=50) Fig. 5.1. Experimental results of processing time are presented in Table 5.1, Table 5.2 and 5.1. Experimental results of processing time are presented in Table 5.1, Table 5.2 and 5. Experimental results of O(1) algorithm and comparison with CB algorithm in FE’
    Table 3.1. Preprocessing time of AEL (subdivision in the direction of k : nx = 10)
    Fig. 6.1. Semidual representation of convex polyhedron The table show six planes with its numbers. On this number we will reference in algorithm 6.1.
    Fig. 3.2. Number of edges in AEL dependent on subdivision in the direction of k (N = 10, ng is 1, 10, 100 and 1000)
    Table 5.3. Theoretical and experimental efficiencies A comparison of theoretical estimations and experimental results is presented in Table 5.3.
    Fig. 5.2. Processing times for different number of clipped lines
    The construction time of AEL is presented in Table 3.1. and Fig. 3.3
    Table 2.1. Representation of geometrical primitives
    The first test is determining the speed of the algorithm with a various number of the polygon facets in dependence on subdivision of dual space. In table and in some graphs there adequate results of CB algorithm are presented . For even type of subdivision of dual space three graphs are presented. Preprocessing graph, processing graph and sum of preprocessing and processing consuming time graph. Very interesting is the third graph. This graph shows an optimal subdivision of the dual space. The shown optimum is relative. It is optimum for sum of preprocessing and processing time, but in some applications we want to minimize the time of processing. For this application type, the presented optimum is improper. Tables and graphs are included in appendix. The tests are computed for ny=n,, nx=2,
    Fig. 5.3. Processing times for different probability of intersection Table 5.5. Processing times for different probability of intersection N = 10, M = 10.000, coefficients of O(1) : n.=10, ng=50
    lable 5.4. Processing times for different number of clipped line Polygon with N = 10, coefficients of O(1) : n.=10, ng=50 Dependence of a processing time of O(1) algorithm on a probability that clipped lines intersect the given polygon for N=10 is shown in Table 5.4 and Fig. 5.2. Experimental results show that O(1) algorithm is faster than CB algorithm if number of clipped lines is greater than 5000. The limit value is the same for all probabilities of intersection of a polygon by clipped line.
    Fig. 3.1. Number of edges in AEL dependent on subdivision in the direction of q (N = 10, nx is 1, 10, 100 and 1000) rMAy ours These conditions guarantee that each list of AEL contains up to three edges. It is necessary to point out that these conditions can extremely increase subdivisions of semidual spaces and memory requirements can be above system possibilities. That is why these conditions cannot be realized. Then it is essential to find an optimal level of subdivision which subdivide the semidual spaces sufficiently, but on the other hand which do not exceed above available memory. Experimental results of space subdivision for a polygon with N = 10 are presented in Fig. 3.1.,Fig. 3.2.
    The processing time of the proposed O(1) algorithm depends on a probability of intersection of the given polygon. It is also presented in Table 5.5 and Fig. 5.3. The time complexity of the CB algorithm is nearly constant, but the more clipped lines intersect the polygon, the more processing time is needed in O(1) algorithm. It is due to the test whether a line intersects a polygon is faster for a line does not intersecting the given polygon than for a line which intersects it.
    descriptionView Paperarrow_downwardDownload
    A Comparison of O(1) and Cyrus-Beck Line Clipping Algorithms in E 2 and E 3
    by Vaclav Skala

    2021

    A comparison of a new algorithm for line clipping in E 2 and E 3 by convex polygon and/or polyhedron with O(1) processing complexity and Cyrus-Beck algorithm is presented. The new algorithm in E 2 is based on dual space representation and... more
    descriptionView Paperarrow_downwardDownload
    A COMPARISON OF A NEW O(1) AND THE CYRUS-BECK LINE CLIPPING ALGORITHMS IN E 2
    by Vaclav Skala

    2021

    A comparison of a new algorithm for line clipping in E 2 for convex polygons with O(1) processing complexity and the Cyrus-Beck algorithm is presented. The algorithm is based on the dual space representation and a space subdivision... more
    descriptionView Paperarrow_downwardDownload
    Line Clipping in E 2 with O(1) Processing Complexity
    by Vaclav Skala

    2021

    A new algorithm for line clipping by convex polygon with O() 1 processing complexity is presented. It is based on dual space representation and space subdivision technique. The suggested algorithm also demonstrates that pre-processing can... more
    descriptionView Paperarrow_downwardDownload
    ALGORITHMS COMPLEXITY AND LINE CLIPPING PROBLEM SOLUTIONS
    by Vaclav Skala

    2021

    Algorithm complexity is very often used for comparison of different algorithms in order to assess theirs properties. Nevertheless there are some other factors like actual speed for the expected applications, memory needed and others that... more
    descriptionView Paperarrow_downwardDownload
    NON-ORTHOGONAL CO-ORDINATES IN COMPUTER GRAPHICS i
    by Vaclav Skala

    2021

    There are many applications that are not naturally based on the orthogonal coordinate systems, like ultrasound imaging, astronomy, mechanical computations etc. In many cases it is necessary to transform the problem formulation to the... more
    So we get the following simple steps: where: r is the distance of the point from the origin and Ag is the angle that defines the rotation. So we get
    Of course, non-trivial computation is needed if this operation should be performed by using the cartesian co-ordinate system or by deriving the transformation formula directly. Nevertheless this operation can be generally split into the following elementary transformations:
    It is well known, that the geometric transformations can be represented by matrices generally, i.e. for the translation we get: It can be seen that there the point x defines also unambiguously a line p that is orthogonal to the line defined by this point and by the origin of the polar co-ordinate system, see fig.1.
    This representation enables us to represent not only the given point but also the given line in the polar co-ordinate system unambiguously.
    The rotation operation is defined in a similar way as the rotation in the Cartesian co-ordinate system. Let us suppose that we want to rotate the point about the orisin with an angele A® It is well known that where: r is the translation parameter. There is also an alternative definition that enables to move points A times, e.g. relatively to the original distance from the origin.
    In the polar co-ordinate system the translation matrix is defined as
    There is a straightforward extension to E® space if the cylindrical co-ordinate system is to be used. We can describe a point by a vector: It can be seen, that the operations shown above, can handle with points as well as with lines because the line is unambiguously defined as dual primitive to the given point. Then the general transformation matrix in E’ case is defined as
    It means that we are able to handle lines in a similar way. We have dealt with geometric transformations for points till now. Everybody can see that the representation of the point A is unambiguous. We can now define this point as a reference point, which lies on the oriented line p and which is perpendicular to the line that passes the line on which the O and A points lie, see fig.4.
    Let us suppose that each element of the array contains an information about the actual edge of the given polygon that is intersected by the i-th wedge that is Ag wide and has a vertex in the origin of the co-ordinate system. The value of the index i can be determined as Let us imagine, that we split the whole interval for the @ values to M very small subintervals equidistantly, see fig.6.
    This algorithm can be even speed up in order to avoid the search with the O(/g N) complexity. This leads to the algorithm with the run-time complexity bellow O(lg N).
    A similar algorithm to this was recently developed for the cartesian co-ordinate system, verified and tested. It proved the O(1) expected run-time complexity and detailed description can be found in [Ska96b]. This algorithm cannot be implemented, as it would require an infinite memory, due to the fact that we presumed that A@ > 0, i.e. M > o. Nevertheless it is possible to determine max.Ad@, i.e. the maximal angle of the wedge, for the given polygon from its geometrical properties. In every case the algorithm must expect that two edges will be tested as some wedge can contain two vertices, see fig.7.
    descriptionView Paperarrow_downwardDownload
    Download research papers for free!
    580 California St., Suite 400
    San Francisco, CA, 94104