Arrangement_on_surface_2/include/CGAL/Arr_polycurve_basic_traits_2.h:   * containing it can be located in O(log n) operations.
Combinatorial_map/doc/Combinatorial_map/Combinatorial_map.txt:It is often necessary to mark darts, for example to retrieve in <I>O(1)</I> if a given dart was already processed during a specific algorithm, for example,  iteration over a given range. Users can also mark specific parts of a combinatorial map (for example mark all the darts belonging to objects having specific semantics). To answer these needs, a `GenericMap` has a certain number of Boolean marks (fixed by the constant \link GenericMap::NB_MARKS `NB_MARKS`\endlink). When one wants to use a Boolean mark, the following methods are available (with `cm` an instance of a combinatorial map):
Combinatorial_map/include/CGAL/Combinatorial_map.h:     * If all the darts are marked or unmarked, this operation takes O(1)
Cone_spanners_2/include/CGAL/Cone_spanners_2/Plane_scan_tree.h: * to be at worst O(log n), and builds the tree from a list at O(nlogn).
Convex_hull_d/include/CGAL/Convex_hull_d.h:  inserting $x$ is $O(|dim| \sum_i k_i)$ and the number of new simplices
Generalized_map/doc/Generalized_map/Generalized_map.txt:It is often necessary to mark darts, for example to retrieve in <I>O(1)</I> if a given dart was already processed during a specific algorithm, for example,  iteration over a given range. Users can also mark specific parts of a generalized map (for example mark all the darts belonging to objects having specific semantics). To answer these needs, a `GeneralizedMap` has a certain number of Boolean marks (fixed by the constant \link GenericMap::NB_MARKS `NB_MARKS`\endlink). When one wants to use a Boolean mark, the following methods are available (with `gm` an instance of a generalized map):
Generalized_map/include/CGAL/Generalized_map.h:     * If all the darts are marked or unmarked, this operation takes O(1)
Inscribed_areas/include/CGAL/Largest_empty_iso_rectangle_2.h:  and remain empty). There are O(n^2) such rectangles. It is done in three
Installation/CHANGES.md:    maximal expected running time *O(2<sup>O(d)</sup> n)* and a fast and
Kernel_d/include/CGAL/Kernel_d/Aff_transformationHd.h:output on a transformation $t$ take time $O(|t.dimension()|^2)$. |dimension()|
Kernel_d/include/CGAL/Kernel_d/Aff_transformationHd.h:requirement is $O(|t.dimension()|^2)$. }*/
Kernel_d/include/CGAL/Kernel_d/DirectionHd.h:output on a direction $d$ take time $O(|d.dimension()|)$. |dimension()|,
Kernel_d/include/CGAL/Kernel_d/DirectionHd.h:requirement is $O(|d.dimension()|)$.  }*/
Kernel_d/include/CGAL/Kernel_d/HyperplaneHd.h:$O(|h.dimension()|)$. coordinate access and |dimension()| take
Kernel_d/include/CGAL/Kernel_d/HyperplaneHd.h:constant time.  The space requirement is $O(|h.dimension()|)$.  }*/
Kernel_d/include/CGAL/Kernel_d/Line_d.h:$O(|l.dimension()|)$. |dimension()|, coordinate and point access, and
Kernel_d/include/CGAL/Kernel_d/Line_d.h:calculation also take time $O(|l.dimension()|)$. The space requirement
Kernel_d/include/CGAL/Kernel_d/Line_d.h:is $O(|l.dimension()|)$.}*/
Kernel_d/include/CGAL/Kernel_d/Matrix__.h:|column| takes time $O(n)$, |row|, |dim1|, |dim2| take constant time,
Kernel_d/include/CGAL/Kernel_d/Matrix__.h:and all other operations take time $O(nm)$.  The space requirement is
Kernel_d/include/CGAL/Kernel_d/Matrix__.h:$O(nm)$.}*/
Kernel_d/include/CGAL/Kernel_d/PointHd.h:output on a point $p$ take time $O(|p.dimension()|)$. |dimension()|,
Kernel_d/include/CGAL/Kernel_d/PointHd.h:requirement for points is $O(|p.dimension()|)$.}*/
Kernel_d/include/CGAL/Kernel_d/Ray_d.h:$O(|r.dimension()|)$. |dimension()|, coordinate and point access, and
Kernel_d/include/CGAL/Kernel_d/Ray_d.h:$O(|r.dimension()|)$.}*/
Kernel_d/include/CGAL/Kernel_d/Segment_d.h:segment $s$ take time $O(|s.dimension()|)$. |dimension()|, coordinate
Kernel_d/include/CGAL/Kernel_d/Segment_d.h:$O(|s.dimension()|)$. The space requirement is $O(|s.dimension()|)$.
Kernel_d/include/CGAL/Kernel_d/Sphere_d.h:$O(|s.dimension()|)$. |dimension()|, point access take constant time.
Kernel_d/include/CGAL/Kernel_d/Sphere_d.h:The space requirement for spheres is $O(|s.dimension()|)$
Kernel_d/include/CGAL/Kernel_d/VectorHd.h:input and output on a vector $v$ take time $O(|v.dimension()|)$.
Kernel_d/include/CGAL/Kernel_d/VectorHd.h:$O(|v.dimension()|)$.}*/
Kernel_d/include/CGAL/Kernel_d/Vector__.h:|NT|. All operations on a vector |v| take time $O(|v.dimension()|)$,
Kernel_d/include/CGAL/Kernel_d/Vector__.h:requirement is $O(|v.dimension()|)$. }*/
Kernel_d/include/CGAL/Linear_algebraHd.h:$O(n^3)$, and all other operations take time $O(nm)$. These time
Minkowski_sum_2/include/CGAL/Polygon_convex_decomposition_2.h: * The O(n^4) optimal strategy for decomposing a polygon into convex
Minkowski_sum_2/include/CGAL/Polygon_convex_decomposition_2.h: * Hertel and Mehlhorn's O(n) approximation strategy for decomposing a
Minkowski_sum_2/include/CGAL/Polygon_convex_decomposition_2.h: * Greene's O(n log(n)) approximation strategy for decomposing a polygon into
Nef_2/include/CGAL/Nef_2/gen_point_location.h:  The expected space requirement is $O(k)$ where $k$ is the sum of the number
Nef_2/include/CGAL/Nef_2/gen_point_location.h:  $O(k \cdot \log k)$, for the |locate|-operations it is $O(\log k)$. The
Nef_2/include/CGAL/Nef_2/gen_point_location.h:  operation |clear| runs in $O(k)$.
Nef_2/include/CGAL/Nef_2/PM_point_locator.h:  initialization which needs worst case $O(n^2)$ time though runtime
Nef_2/include/CGAL/Nef_2/PM_point_locator.h:  query structure is subsumed in the storage space $O(n)$ of the input
Nef_2/include/CGAL/Nef_2/PM_point_locator.h:  persistent dictionaries.  Then $T_{pl}(n) = O( \log(n) )$. If CGAL is
Nef_2/include/CGAL/Nef_2/PM_point_locator.h:  ray shot is expected to be $O( \sqrt{n} )$.}*/
Nef_2/include/CGAL/Nef_2/Polynomial.h:$O(d*T(NT))$, multiplication is quadratic in the maximal degree of the
Nef_2/include/CGAL/Nef_2/Polynomial.h:$O(d*T(int))$, multiplication is quadratic in the maximal degree of the
Nef_2/include/CGAL/Nef_2/Polynomial.h:$O(d*T(double))$, multiplication is quadratic in the maximal degree of the
Nef_2/include/CGAL/Nef_polyhedron_2.h:  operations and comparison operations take time $O(n \log n)$ where $n$
Nef_2/include/CGAL/Nef_polyhedron_2.h:  operation. Preprocessing takes time $O(N^2)$, the sub-linear point
Nef_2/include/CGAL/Nef_polyhedron_2.h:  polyhedron) the theory provides a $O(\sqrt{n})$ bound for the number
Nef_3/include/CGAL/Nef_polyhedron_3.h:  $O(N^2)$ where $N$ is the size of the output plus the size of the
Nef_S2/include/CGAL/Nef_polyhedron_S2.h:  operations and comparison operations take time $O(n \log n)$ where $n$
Orthtree/doc/Orthtree/Orthtree.txt:Both nearest neighbor algorithms have a theoretical complexity of O(log(n)),
Partition_2/include/CGAL/Partition_2/Vertex_visibility_graph_2.h:    The running time is $O(n^2)$ with linear space requirements.
Polygon/include/CGAL/Polygon_2_algorithms.h:/// The running time is `O(n log n)`, where n is the number of vertices of the
STL_Extension/doc/STL_Extension/CGAL/Compact_container.h:`O(capacity())` time, not `size()`. In the case where the container
STL_Extension/doc/STL_Extension/CGAL/Compact_container.h:The time complexity is O(`cc`.`capacity()`-`cc`.`size()`).
STL_Extension/doc/STL_Extension/CGAL/Concurrent_compact_container.h:`O(capacity())` time, not `size()`. In the case where the container
STL_Extension/doc/STL_Extension/CGAL/Concurrent_compact_container.h:The time complexity is O(`ccc`.`capacity()`-`ccc`.`size()`).
STL_Extension/include/CGAL/Multiset.h:   * Default constructor. [takes O(1) operations]
STL_Extension/include/CGAL/Multiset.h:   * Constructor with a comparison object. [takes O(1) operations]
STL_Extension/include/CGAL/Multiset.h:   * Copy constructor. [takes O(n) operations]
STL_Extension/include/CGAL/Multiset.h:   * [takes O(n log n) operations]
STL_Extension/include/CGAL/Multiset.h:   * Destructor. [takes O(n) operations]
STL_Extension/include/CGAL/Multiset.h:   * Assignment operator. [takes O(n) operations]
STL_Extension/include/CGAL/Multiset.h:   * Swap two trees. [takes O(1) operations]
STL_Extension/include/CGAL/Multiset.h:   * Test two trees for equality. [takes O(n) operations]
STL_Extension/include/CGAL/Multiset.h:   * Check if our tree is lexicographically smaller. [takes O(n) operations]
STL_Extension/include/CGAL/Multiset.h:   * Get the size of the tree. [takes O(1) operations, unless the tree
STL_Extension/include/CGAL/Multiset.h:   * was involved in a split operation, then it may take O(n) time.]
STL_Extension/include/CGAL/Multiset.h:   * Insert an object into the tree. [takes O(log n) operations]
STL_Extension/include/CGAL/Multiset.h:   * Insert a range of k objects into the tree. [takes O(k log n) operations]
STL_Extension/include/CGAL/Multiset.h:   * [takes O(log n) operations at worst-case, but only O(1) amortized]
STL_Extension/include/CGAL/Multiset.h:   * [takes O(log n) operations at worst-case, but only O(1) amortized]
STL_Extension/include/CGAL/Multiset.h:   * [takes O(log n) operations at worst-case, but only O(1) amortized]
STL_Extension/include/CGAL/Multiset.h:   * Erase objects from the tree. [takes O(log n) operations]
STL_Extension/include/CGAL/Multiset.h:   * [takes O(log n) operations at worst-case, but only O(1) amortized]
STL_Extension/include/CGAL/Multiset.h:   * Clear the contents of the tree. [takes O(n) operations]
STL_Extension/include/CGAL/Multiset.h:   * [takes O(log n) operations]
STL_Extension/include/CGAL/Multiset.h:   * [takes O(log n) operations]
STL_Extension/include/CGAL/Multiset.h:   * [takes O(log n + d) operations]
STL_Extension/include/CGAL/Multiset.h:   * (non-const version). [takes O(log n) operations]
STL_Extension/include/CGAL/Multiset.h:   * (non-const version). [takes O(log n) operations]
STL_Extension/include/CGAL/Multiset.h:   * (non-const version). [takes O(log n) operations]
STL_Extension/include/CGAL/Multiset.h:   * (const version). [takes O(log n) operations]
STL_Extension/include/CGAL/Multiset.h:   * (const version). [takes O(log n) operations]
STL_Extension/include/CGAL/Multiset.h:   * (const version). [takes O(log n) operations]
STL_Extension/include/CGAL/Multiset.h:   * (non-const version). [takes O(log n + d) operations]
STL_Extension/include/CGAL/Multiset.h:   * (const version). [takes O(log n + d) operations]
STL_Extension/include/CGAL/Multiset.h:   * [takes O(1) operations]
STL_Extension/include/CGAL/Multiset.h:   * [takes O(1) operations]
STL_Extension/include/CGAL/Multiset.h:   * than the maximal object of this tree. [takes O(log n) operations]
STL_Extension/include/CGAL/Multiset.h:   * a new output tree. [takes O(log n) operations]
STL_Extension/include/CGAL/Multiset.h:   * [position, end) form a new output tree. [takes O(log n) operations]
STL_Extension/include/CGAL/Multiset.h:   * Get the height of the tree. [takes O(n) operations]
STL_Extension/include/CGAL/Multiset.h:   * Get the black-height of the tree. [takes O(1) operations]
Solver_interface/include/CGAL/Eigen_sparse_matrix.h:  /// - O(log(n)) if the matrix is already built.
Solver_interface/include/CGAL/Eigen_sparse_matrix.h:  /// - O(n) if the matrix is not built.
Surface_mesh_segmentation/include/CGAL/Surface_mesh_segmentation/internal/K_means_clustering.h:   * where k = number of centers = complexity is O(k log k), and mem overhead is O(k)
Triangulation_3/demo/Triangulation_3/typedefs.h: *       Fast_location offers O(logn) time point location, using additional data structure,
Triangulation_3/demo/Triangulation_3/typedefs.h: *     and point location is then O(n^(1/3)) time