8000 [3.11] gh-113664: Improve style of Big O notation (GH-113695) (GH-113… · python/cpython@c92a473 · GitHub
[go: up one dir, main page]
Skip to content

Commit c92a473

Browse files
serhiy-storchakaserhiy-storchaka
authored
[3.11] gh-113664: Improve style of Big O notation (GH-113695) (GH-113910)
Use cursive to make it looking like mathematic formulas. (cherry picked from commit a862981)
1 parent b4a6bbd commit c92a473

14 files changed

+25
-25
lines changed

‎Doc/faq/design.rst

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -449,7 +449,7 @@ on the key and a per-process seed; for example, "Python" could hash to
449449
to 1142331976. The hash code is then used to calculate a location in an
450450
internal array where the value will be stored. Assuming that you're storing
451451
keys that all have different hash values, this means that dictionaries take
452-
constant time -- O(1), in Big-O notation -- to retrieve a key.
452+
constant time -- *O*\ (1), in Big-O notation -- to retrieve a key.
453453

454454

455455
Why must dictionary keys be immutable?

‎Doc/glossary.rst

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -741,7 +741,7 @@ Glossary
741741
list
742742
A built-in Python :term:`sequence`. Despite its name it is more akin
743743
to an array in other languages than to a linked list since access to
744-
elements is O(1).
744+
elements is *O*\ (1).
745745

746746
list comprehension
747747
A compact way to process all or part of the elements in a sequence and

‎Doc/library/asyncio-policy.rst

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -226,7 +226,7 @@ implementation used by the asyncio event loop:
226226

227227
It works reliably even when the asyncio event loop is run in a non-main OS thread.
228228

229-
There is no noticeable overhead when handling a big number of children (*O(1)* each
229+
There is no noticeable overhead when handling a big number of children (*O*\ (1) each
230230
time a child terminates), but starting a thread per process requires extra memory.
231231

232232
This watcher is used by default.
@@ -246,7 +246,7 @@ implementation used by the asyncio event loop:
246246
watcher is installed.
247247

248248
The solution is safe but it has a significant overhead when
249-
handling a big number of processes (*O(n)* each time a
249+
handling a big number of processes (*O*\ (*n*) each time a
250250
:py:data:`SIGCHLD` is received).
251251

252252
.. versionadded:: 3.8
@@ -260,7 +260,7 @@ implementation used by the asyncio event loop:
260260
The watcher avoids disrupting other code spawning processes
261261
by polling every process explicitly on a :py:data:`SIGCHLD` signal.
262262

263-
This solution is as safe as :class:`MultiLoopChildWatcher` and has the same *O(N)*
263+
This solution is as safe as :class:`MultiLoopChildWatcher` and has the same *O*\ (*n*)
264264
complexity but requires a running event loop in the main thread to work.
265265

266266
.. class:: FastChildWatcher
@@ -270,7 +270,7 @@ implementation used by the asyncio event loop:
270270
processes and waiting for their termination.
271271

272272
There is no noticeable overhead when handling a big number of
273-
children (*O(1)* each time a child terminates).
273+
children (*O*\ (1) each time a child terminates).
274274

275275
This solution requires a running event loop in the main thread to work, as
276276
:class:`SafeChildWatcher`.

‎Doc/library/bisect.rst

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -79,7 +79,7 @@ The following functions are provided:
7979
To support inserting records in a table, the *key* function (if any) is
8080
applied to *x* for the search step but not for the insertion step.
8181

82-
Keep in mind that the ``O(log n)`` search is dominated by the slow O(n)
82+
Keep in mind that the *O*\ (log *n*) search is dominated by the slow *O*\ (*n*)
8383
insertion step.
8484

8585
.. versionchanged:: 3.10
@@ -99,7 +99,7 @@ The following functions are provided:
9999
To support inserting records in a table, the *key* function (if any) is
100100
applied to *x* for the search step but not for the insertion step.
101101

102-
Keep in mind that the ``O(log n)`` search is dominated by the slow O(n)
102+
Keep in mind that the *O*\ (log *n*) search is dominated by the slow *O*\ (*n*)
103103
insertion step.
104104

105105
.. versionchanged:: 3.10
@@ -115,7 +115,7 @@ thoughts in mind:
115115
* Bisection is effective for searching ranges of values.
116116
For locating specific values, dictionaries are more performant.
117117

118-
* The *insort()* functions are ``O(n)`` because the logarithmic search step
118+
* The *insort()* functions are *O*\ (*n*) because the logarithmic search step
119119
is dominated by the linear time insertion step.
120120

121121
* The search functions are stateless and discard key function results after

‎Doc/library/collections.rst

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -457,10 +457,10 @@ or subtracting from an empty counter.
457457
Deques are a generalization of stacks and queues (the name is pronounced "deck"
458458
and is short for "double-ended queue"). Deques support thread-safe, memory
459459
efficient appends and pops from either side of the deque with approximately the
460-
same O(1) performance in either direction.
460+
same *O*\ (1) performance in either direction.
461461

462462
Though :class:`list` objects support similar operations, they are optimized for
463-
fast fixed-length operations and incur O(n) memory movement costs for
463+
fast fixed-length operations and incur *O*\ (*n*) memory movement costs for
464464
``pop(0)`` and ``insert(0, v)`` operations which change both the size and
465465
position of the underlying data representation.
466466

@@ -584,7 +584,7 @@ or subtracting from an empty counter.
584584
In addition to the above, deques support iteration, pickling, ``len(d)``,
585585
``reversed(d)``, ``copy.copy(d)``, ``copy.deepcopy(d)``, membership testing with
586586
the :keyword:`in` operator, and subscript references such as ``d[0]`` to access
587-
the first element. Indexed access is O(1) at both ends but slows to O(n) in
587+
the first element. Indexed access is *O*\ (1) at both ends but slows to *O*\ (*n*) in
588588
the middle. For fast random access, use lists instead.
589589

590590
Starting in version 3.5, deques support ``__add__()``, ``__mul__()``,

‎Doc/library/contextvars.rst

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -131,7 +131,7 @@ Manual Context Management
131131
ctx: Context = copy_context()
132132
print(list(ctx.items()))
133133

134-
The function has an O(1) complexity, i.e. works equally fast for
134+
The function has an *O*\ (1) complexity, i.e. works equally fast for
135135
contexts with a few context variables and for contexts that have
136136
a lot of them.
137137

‎Doc/library/heapq.rst

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -270,7 +270,7 @@ winner. The simplest algorithmic way to remove it and find the "next" winner is
270270
to move some loser (let's say cell 30 in the diagram above) into the 0 position,
271271
and then percolate this new 0 down the tree, exchanging values, until the
272272
invariant is re-established. This is clearly logarithmic on the total number of
273-
items in the tree. By iterating over all items, you get an O(n log n) sort.
273+
items in the tree. By iterating over all items, you get an *O*\ (*n* log *n*) sort.
274274

275275
A nice feature of this sort is that you can efficiently insert new items while
276276
the sort is going on, provided that the inserted items are not "better" than the

‎Doc/library/select.rst

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -185,8 +185,8 @@ The module defines the following:
185185
-----------------------------
186186

187187
Solaris and derivatives have ``/dev/poll``. While :c:func:`!select` is
188-
O(highest file descriptor) and :c:func:`!poll` is O(number of file
189-
descriptors), ``/dev/poll`` is O(active file descriptors).
188+
*O*\ (*highest file descriptor*) and :c:func:`!poll` is *O*\ (*number of file
189+
descriptors*), ``/dev/poll`` is *O*\ (*active file descriptors*).
190190

191191
``/dev/poll`` behaviour is very close to the standard :c:func:`!poll`
192192
object.
@@ -381,8 +381,8 @@ scalability for network servers that service many, many clients at the same
381381
time. :c:func:`!poll` scales better because the system call only requires listing
382382
the file descriptors of interest, while :c:func:`!select` builds a bitmap, turns
383383
on bits for the fds of interest, and then afterward the whole bitmap has to be
384-
linearly scanned again. :c:func:`!select` is O(highest file descriptor), while
385-
:c:func:`!poll` is O(number of file descriptors).
384+
linearly scanned again. :c:func:`!select` is *O*\ (*highest file descriptor*), while
385+
:c:func:`!poll` is *O*\ (*number of file descriptors*).
386386

387387

388388
.. method:: poll.register(fd[, eventmask])

‎Doc/reference/datamodel.rst

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1854,7 +1854,7 @@ Basic customization
18541854

18551855
This is intended to provide protection against a denial-of-service caused
18561856
by carefully chosen inputs that exploit the worst case performance of a
1857-
dict insertion, O(n\ :sup:`2`) complexity. See
1857+
dict insertion, *O*\ (*n*\ :sup:`2`) complexity. See
18581858
http://ocert.org/advisories/ocert-2011-003.html for details.
18591859

18601860
Changing hash values affects the iteration order of sets.

‎Doc/using/cmdline.rst

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -366,7 +366,7 @@ Miscellaneous options
366366

367367
Hash randomization is intended to provide protection against a
368368
denial-of-service caused by carefully chosen inputs that exploit the worst
369-
case performance of a dict construction, O(n\ :sup:`2`) complexity. See
369+
case performance of a dict construction, *O*\ (*n*\ :sup:`2`) complexity. See
370370
http://ocert.org/advisories/ocert-2011-003.html for details.
371371

372372
:envvar:`PYTHONHASHSEED` allows you to set a fixed value for the hash

‎Doc/whatsnew/2.3.rst

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1196,7 +1196,7 @@ Optimizations
11961196

11971197
* Multiplication of large long integers is now much faster thanks to an
11981198
implementation of Karatsuba multiplication, an algorithm that scales better than
1199-
the O(n\*n) required for the grade-school multiplication algorithm. (Original
1199+
the *O*\ (*n*\ :sup:`2`) required for the grade-school multiplication algorithm. (Original
12001200
patch by Christopher A. Craig, and significantly reworked by Tim Peters.)
12011201

12021202
* The ``SET_LINENO`` opcode is now gone. This may provide a small speed
@@ -1308,7 +1308,7 @@ complete list of changes, or look through the CVS logs for all the details.
13081308
partially sorted order such that, for every index *k*, ``heap[k] <=
13091309
heap[2*k+1]`` and ``heap[k] <= heap[2*k+2]``. This makes it quick to remove the
13101310
smallest item, and inserting a new item while maintaining the heap property is
1311-
O(lg n). (See https://xlinux.nist.gov/dads//HTML/priorityque.html for more
1311+
*O*\ (log *n*). (See https://xlinux.nist.gov/dads//HTML/priorityque.html for more
13121312
information about the priority queue data structure.)
13131313

13141314
The :mod:`heapq` module provides :func:`~heapq.heappush` and :func:`~heapq.heappop` functions

‎Doc/whatsnew/2.7.rst

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -282,7 +282,7 @@ How does the :class:`~collections.OrderedDict` work? It maintains a
282282
doubly linked list of keys, appending new keys to the list as they're inserted.
283283
A secondary dictionary maps keys to their corresponding list node, so
284284
deletion doesn't have to traverse the entire linked list and therefore
285-
remains O(1).
285+
remains *O*\ (1).
286286

287287
The standard library now supports use of ordered dictionaries in several
288288
modules.

‎Doc/whatsnew/3.3.rst

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -174,7 +174,7 @@ Features
174174
b or c are now hashable. (Contributed by Antoine Pitrou in :issue:`13411`.)
175175

176176
* Arbitrary slicing of any 1-D arrays type is supported. For example, it
177-
is now possible to reverse a memoryview in O(1) by using a negative step.
177+
is now possible to reverse a memoryview in *O*\ (1) by using a negative step.
178178

179179
API changes
180180
-----------

‎Misc/NEWS.d/3.5.0a1.rst

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2648,7 +2648,7 @@ module.
26482648
.. nonce: THJSYB
26492649
.. section: Library
26502650
2651-
Changed FeedParser feed() to avoid O(N\ :sup:`2`) behavior when parsing long line.
2651+
Changed FeedParser feed() to avoid *O*\ (*n*\ :sup:`2`) behavior when parsing long line.
26522652
Original patch by Raymond Hettinger.
26532653

26542654
..

0 commit comments

Comments
 (0)
0