diff options
| author | Manish Goregaokar <manishsmail@gmail.com> | 2021-09-25 18:22:20 -0700 |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2021-09-25 18:22:20 -0700 |
| commit | 653dcaac2b9b647ebcf417dbc1e55341c10160b9 (patch) | |
| tree | bad03149285ff2b553f5dafb85379089fb2bba9d /library/std/src | |
| parent | c118d8b79b2e10d6922423ecb6162ffe8f5d07fb (diff) | |
| parent | 956f87fb04f589ac2fbe262a043c9f3cad6b2ac0 (diff) | |
| download | rust-653dcaac2b9b647ebcf417dbc1e55341c10160b9.tar.gz rust-653dcaac2b9b647ebcf417dbc1e55341c10160b9.zip | |
Rollup merge of #89216 - r00ster91:bigo, r=dtolnay
Consistent big O notation This makes the big O time complexity notation in places with markdown support more consistent. Inspired by #89210
Diffstat (limited to 'library/std/src')
| -rw-r--r-- | library/std/src/collections/mod.rs | 18 | ||||
| -rw-r--r-- | library/std/src/ffi/mod.rs | 4 |
2 files changed, 11 insertions, 11 deletions
diff --git a/library/std/src/collections/mod.rs b/library/std/src/collections/mod.rs index 0c65caa1bdf..6ca0525cdbe 100644 --- a/library/std/src/collections/mod.rs +++ b/library/std/src/collections/mod.rs @@ -97,11 +97,11 @@ //! //! ## Sequences //! -//! | | get(i) | insert(i) | remove(i) | append | split_off(i) | -//! |----------------|----------------|-----------------|----------------|--------|----------------| -//! | [`Vec`] | O(1) | O(n-i)* | O(n-i) | O(m)* | O(n-i) | -//! | [`VecDeque`] | O(1) | O(min(i, n-i))* | O(min(i, n-i)) | O(m)* | O(min(i, n-i)) | -//! | [`LinkedList`] | O(min(i, n-i)) | O(min(i, n-i)) | O(min(i, n-i)) | O(1) | O(min(i, n-i)) | +//! | | get(i) | insert(i) | remove(i) | append | split_off(i) | +//! |----------------|------------------------|-------------------------|------------------------|-----------|------------------------| +//! | [`Vec`] | *O*(1) | *O*(*n*-*i*)* | *O*(*n*-*i*) | *O*(*m*)* | *O*(*n*-*i*) | +//! | [`VecDeque`] | *O*(1) | *O*(min(*i*, *n*-*i*))* | *O*(min(*i*, *n*-*i*)) | *O*(*m*)* | *O*(min(*i*, *n*-*i*)) | +//! | [`LinkedList`] | *O*(min(*i*, *n*-*i*)) | *O*(min(*i*, *n*-*i*)) | *O*(min(*i*, *n*-*i*)) | *O*(1) | *O*(min(*i*, *n*-*i*)) | //! //! Note that where ties occur, [`Vec`] is generally going to be faster than [`VecDeque`], and //! [`VecDeque`] is generally going to be faster than [`LinkedList`]. @@ -110,10 +110,10 @@ //! //! For Sets, all operations have the cost of the equivalent Map operation. //! -//! | | get | insert | remove | range | append | -//! |--------------|-----------|-----------|-----------|-----------|--------| -//! | [`HashMap`] | O(1)~ | O(1)~* | O(1)~ | N/A | N/A | -//! | [`BTreeMap`] | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n+m) | +//! | | get | insert | remove | range | append | +//! |--------------|---------------|---------------|---------------|---------------|--------------| +//! | [`HashMap`] | *O*(1)~ | *O*(1)~* | *O*(1)~ | N/A | N/A | +//! | [`BTreeMap`] | *O*(log(*n*)) | *O*(log(*n*)) | *O*(log(*n*)) | *O*(log(*n*)) | *O*(*n*+*m*) | //! //! # Correct and Efficient Usage of Collections //! diff --git a/library/std/src/ffi/mod.rs b/library/std/src/ffi/mod.rs index 50708c1f5fb..82a76aa73c5 100644 --- a/library/std/src/ffi/mod.rs +++ b/library/std/src/ffi/mod.rs @@ -43,8 +43,8 @@ //! terminator, so the buffer length is really `len+1` characters. //! Rust strings don't have a nul terminator; their length is always //! stored and does not need to be calculated. While in Rust -//! accessing a string's length is a `O(1)` operation (because the -//! length is stored); in C it is an `O(length)` operation because the +//! accessing a string's length is an *O*(1) operation (because the +//! length is stored); in C it is an *O*(*n*) operation because the //! length needs to be computed by scanning the string for the nul //! terminator. //! |