diff options
Diffstat (limited to 'src/liballoc')
| -rw-r--r-- | src/liballoc/collections/binary_heap.rs | 26 | ||||
| -rw-r--r-- | src/liballoc/collections/linked_list.rs | 20 | ||||
| -rw-r--r-- | src/liballoc/collections/vec_deque.rs | 16 | ||||
| -rw-r--r-- | src/liballoc/string.rs | 8 |
4 files changed, 35 insertions, 35 deletions
diff --git a/src/liballoc/collections/binary_heap.rs b/src/liballoc/collections/binary_heap.rs index 15313e333ce..8398cfa3bd3 100644 --- a/src/liballoc/collections/binary_heap.rs +++ b/src/liballoc/collections/binary_heap.rs @@ -1,9 +1,9 @@ //! A priority queue implemented with a binary heap. //! -//! Insertion and popping the largest element have `O(log(n))` time complexity. -//! Checking the largest element is `O(1)`. Converting a vector to a binary heap -//! can be done in-place, and has `O(n)` complexity. A binary heap can also be -//! converted to a sorted vector in-place, allowing it to be used for an `O(n * log(n))` +//! Insertion and popping the largest element have *O*(log(*n*)) time complexity. +//! Checking the largest element is *O*(1). Converting a vector to a binary heap +//! can be done in-place, and has *O*(*n*) complexity. A binary heap can also be +//! converted to a sorted vector in-place, allowing it to be used for an *O*(*n* \* log(*n*)) //! in-place heapsort. //! //! # Examples @@ -235,7 +235,7 @@ use super::SpecExtend; /// /// | [push] | [pop] | [peek]/[peek\_mut] | /// |--------|-----------|--------------------| -/// | O(1)~ | O(log(n)) | O(1) | +/// | O(1)~ | *O*(log(*n*)) | *O*(1) | /// /// The value for `push` is an expected cost; the method documentation gives a /// more detailed analysis. @@ -398,7 +398,7 @@ impl<T: Ord> BinaryHeap<T> { /// /// # Time complexity /// - /// Cost is `O(1)` in the worst case. + /// Cost is *O*(1) in the worst case. #[stable(feature = "binary_heap_peek_mut", since = "1.12.0")] pub fn peek_mut(&mut self) -> Option<PeekMut<'_, T>> { if self.is_empty() { None } else { Some(PeekMut { heap: self, sift: true }) } @@ -422,7 +422,7 @@ impl<T: Ord> BinaryHeap<T> { /// /// # Time complexity /// - /// The worst case cost of `pop` on a heap containing *n* elements is `O(log(n))`. + /// The worst case cost of `pop` on a heap containing *n* elements is *O*(log(*n*)). #[stable(feature = "rust1", since = "1.0.0")] pub fn pop(&mut self) -> Option<T> { self.data.pop().map(|mut item| { @@ -455,15 +455,15 @@ impl<T: Ord> BinaryHeap<T> { /// /// The expected cost of `push`, averaged over every possible ordering of /// the elements being pushed, and over a sufficiently large number of - /// pushes, is `O(1)`. This is the most meaningful cost metric when pushing + /// pushes, is *O*(1). This is the most meaningful cost metric when pushing /// elements that are *not* already in any sorted pattern. /// /// The time complexity degrades if elements are pushed in predominantly /// ascending order. In the worst case, elements are pushed in ascending - /// sorted order and the amortized cost per push is `O(log(n))` against a heap + /// sorted order and the amortized cost per push is *O*(log(*n*)) against a heap /// containing *n* elements. /// - /// The worst case cost of a *single* call to `push` is `O(n)`. The worst case + /// The worst case cost of a *single* call to `push` is *O*(*n*). The worst case /// occurs when capacity is exhausted and needs a resize. The resize cost /// has been amortized in the previous figures. #[stable(feature = "rust1", since = "1.0.0")] @@ -643,7 +643,7 @@ impl<T: Ord> BinaryHeap<T> { /// The remaining elements will be removed on drop in heap order. /// /// Note: - /// * `.drain_sorted()` is `O(n * log(n))`; much slower than `.drain()`. + /// * `.drain_sorted()` is *O*(*n* \* log(*n*)); much slower than `.drain()`. /// You should use the latter for most cases. /// /// # Examples @@ -756,7 +756,7 @@ impl<T> BinaryHeap<T> { /// /// # Time complexity /// - /// Cost is `O(1)` in the worst case. + /// Cost is *O*(1) in the worst case. #[stable(feature = "rust1", since = "1.0.0")] pub fn peek(&self) -> Option<&T> { self.data.get(0) @@ -1312,7 +1312,7 @@ unsafe impl<T: Ord> TrustedLen for DrainSorted<'_, T> {} impl<T: Ord> From<Vec<T>> for BinaryHeap<T> { /// Converts a `Vec<T>` into a `BinaryHeap<T>`. /// - /// This conversion happens in-place, and has `O(n)` time complexity. + /// This conversion happens in-place, and has *O*(*n*) time complexity. fn from(vec: Vec<T>) -> BinaryHeap<T> { let mut heap = BinaryHeap { data: vec }; heap.rebuild(); diff --git a/src/liballoc/collections/linked_list.rs b/src/liballoc/collections/linked_list.rs index 36b5785fdf6..1f875f6c521 100644 --- a/src/liballoc/collections/linked_list.rs +++ b/src/liballoc/collections/linked_list.rs @@ -404,7 +404,7 @@ impl<T> LinkedList<T> { /// This reuses all the nodes from `other` and moves them into `self`. After /// this operation, `other` becomes empty. /// - /// This operation should compute in `O(1)` time and `O(1)` memory. + /// This operation should compute in *O*(1) time and *O*(1) memory. /// /// # Examples /// @@ -561,7 +561,7 @@ impl<T> LinkedList<T> { /// Returns `true` if the `LinkedList` is empty. /// - /// This operation should compute in `O(1)` time. + /// This operation should compute in *O*(1) time. /// /// # Examples /// @@ -582,7 +582,7 @@ impl<T> LinkedList<T> { /// Returns the length of the `LinkedList`. /// - /// This operation should compute in `O(1)` time. + /// This operation should compute in *O*(1) time. /// /// # Examples /// @@ -608,7 +608,7 @@ impl<T> LinkedList<T> { /// Removes all elements from the `LinkedList`. /// - /// This operation should compute in `O(n)` time. + /// This operation should compute in *O*(*n*) time. /// /// # Examples /// @@ -751,7 +751,7 @@ impl<T> LinkedList<T> { /// Adds an element first in the list. /// - /// This operation should compute in `O(1)` time. + /// This operation should compute in *O*(1) time. /// /// # Examples /// @@ -774,7 +774,7 @@ impl<T> LinkedList<T> { /// Removes the first element and returns it, or `None` if the list is /// empty. /// - /// This operation should compute in `O(1)` time. + /// This operation should compute in *O*(1) time. /// /// # Examples /// @@ -797,7 +797,7 @@ impl<T> LinkedList<T> { /// Appends an element to the back of a list. /// - /// This operation should compute in `O(1)` time. + /// This operation should compute in *O*(1) time. /// /// # Examples /// @@ -817,7 +817,7 @@ impl<T> LinkedList<T> { /// Removes the last element from a list and returns it, or `None` if /// it is empty. /// - /// This operation should compute in `O(1)` time. + /// This operation should compute in *O*(1) time. /// /// # Examples /// @@ -838,7 +838,7 @@ impl<T> LinkedList<T> { /// Splits the list into two at the given index. Returns everything after the given index, /// including the index. /// - /// This operation should compute in `O(n)` time. + /// This operation should compute in *O*(*n*) time. /// /// # Panics /// @@ -894,7 +894,7 @@ impl<T> LinkedList<T> { /// Removes the element at the given index and returns it. /// - /// This operation should compute in `O(n)` time. + /// This operation should compute in *O*(*n*) time. /// /// # Panics /// Panics if at >= len diff --git a/src/liballoc/collections/vec_deque.rs b/src/liballoc/collections/vec_deque.rs index 15f3a94ca2d..7d2625b7f34 100644 --- a/src/liballoc/collections/vec_deque.rs +++ b/src/liballoc/collections/vec_deque.rs @@ -1,7 +1,7 @@ //! A double-ended queue implemented with a growable ring buffer. //! -//! This queue has `O(1)` amortized inserts and removals from both ends of the -//! container. It also has `O(1)` indexing like a vector. The contained elements +//! This queue has *O*(1) amortized inserts and removals from both ends of the +//! container. It also has *O*(1) indexing like a vector. The contained elements //! are not required to be copyable, and the queue will be sendable if the //! contained type is sendable. @@ -1422,7 +1422,7 @@ impl<T> VecDeque<T> { /// Removes an element from anywhere in the `VecDeque` and returns it, /// replacing it with the first element. /// - /// This does not preserve ordering, but is `O(1)`. + /// This does not preserve ordering, but is *O*(1). /// /// Returns `None` if `index` is out of bounds. /// @@ -1457,7 +1457,7 @@ impl<T> VecDeque<T> { /// Removes an element from anywhere in the `VecDeque` and returns it, replacing it with the /// last element. /// - /// This does not preserve ordering, but is `O(1)`. + /// This does not preserve ordering, but is *O*(1). /// /// Returns `None` if `index` is out of bounds. /// @@ -2241,7 +2241,7 @@ impl<T> VecDeque<T> { /// /// # Complexity /// - /// Takes `O(min(mid, len() - mid))` time and no extra space. + /// Takes `*O*(min(mid, len() - mid))` time and no extra space. /// /// # Examples /// @@ -2284,7 +2284,7 @@ impl<T> VecDeque<T> { /// /// # Complexity /// - /// Takes `O(min(k, len() - k))` time and no extra space. + /// Takes `*O*(min(k, len() - k))` time and no extra space. /// /// # Examples /// @@ -2986,7 +2986,7 @@ impl<T> From<VecDeque<T>> for Vec<T> { /// [`Vec<T>`]: crate::vec::Vec /// [`VecDeque<T>`]: crate::collections::VecDeque /// - /// This never needs to re-allocate, but does need to do `O(n)` data movement if + /// This never needs to re-allocate, but does need to do *O*(*n*) data movement if /// the circular buffer doesn't happen to be at the beginning of the allocation. /// /// # Examples @@ -2994,7 +2994,7 @@ impl<T> From<VecDeque<T>> for Vec<T> { /// ``` /// use std::collections::VecDeque; /// - /// // This one is O(1). + /// // This one is *O*(1). /// let deque: VecDeque<_> = (1..5).collect(); /// let ptr = deque.as_slices().0.as_ptr(); /// let vec = Vec::from(deque); diff --git a/src/liballoc/string.rs b/src/liballoc/string.rs index 13ef94dee23..dfd2084c254 100644 --- a/src/liballoc/string.rs +++ b/src/liballoc/string.rs @@ -1187,7 +1187,7 @@ impl String { /// Removes a [`char`] from this `String` at a byte position and returns it. /// - /// This is an `O(n)` operation, as it requires copying every element in the + /// This is an *O*(*n*) operation, as it requires copying every element in the /// buffer. /// /// # Panics @@ -1289,7 +1289,7 @@ impl String { /// Inserts a character into this `String` at a byte position. /// - /// This is an `O(n)` operation as it requires copying every element in the + /// This is an *O*(*n*) operation as it requires copying every element in the /// buffer. /// /// # Panics @@ -1338,7 +1338,7 @@ impl String { /// Inserts a string slice into this `String` at a byte position. /// - /// This is an `O(n)` operation as it requires copying every element in the + /// This is an *O*(*n*) operation as it requires copying every element in the /// buffer. /// /// # Panics @@ -1996,7 +1996,7 @@ impl hash::Hash for String { /// /// This consumes the `String` on the left-hand side and re-uses its buffer (growing it if /// necessary). This is done to avoid allocating a new `String` and copying the entire contents on -/// every operation, which would lead to `O(n^2)` running time when building an `n`-byte string by +/// every operation, which would lead to *O*(*n*^2) running time when building an *n*-byte string by /// repeated concatenation. /// /// The string on the right-hand side is only borrowed; its contents are copied into the returned |