From cb8ce9d9e543ccf16a2f0a04e47a3691af10d5a6 Mon Sep 17 00:00:00 2001
From: Jacob Asper <jacobasper191@gmail.com>
Date: Fri, 16 Feb 2024 09:41:48 -0500
Subject: time complexity for push

---
 library/alloc/src/vec/mod.rs | 7 +++++++
 1 file changed, 7 insertions(+)

(limited to 'library/alloc/src/vec')

diff --git a/library/alloc/src/vec/mod.rs b/library/alloc/src/vec/mod.rs
index 08e3cdedc66..7bdf92053f1 100644
--- a/library/alloc/src/vec/mod.rs
+++ b/library/alloc/src/vec/mod.rs
@@ -1912,6 +1912,13 @@ impl<T, A: Allocator> Vec<T, A> {
     /// vec.push(3);
     /// assert_eq!(vec, [1, 2, 3]);
     /// ```
+    ///
+    /// # Time complexity
+    ///
+    /// Takes amortized *O*(1) time. If the vector's length would exceed its capacity after
+    /// the push,*O*(*capacity*) space is allocated, doubling the capacity and
+    /// taking *O*(*capacity*) time. This expensive operation is offset by the
+    /// *capacity* *O*(1) insertions it allows.
     #[cfg(not(no_global_oom_handling))]
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
-- 
cgit 1.4.1-3-g733a5