# F(n) = \Left\lceil \Frac{n}{4}\right\rceil^2  URL:: https://brilliant.org/courses/computer-science-algorithms/the-speed-of-algorithms-2/more-big-o/3/ Author:: brilliant.org ## Highlights > The picture of Big OOO isn't a bunch of separate buckets: instead, it looks like a nesting doll. All the functions in O(n)O(n)O(n) also appear in O(n2)O(n^2)O(n2). ([View Highlight](https://read.readwise.io/read/01ga7fexj2qbrfbpep87reh89m)) > Although the step function f(n)f(n)f(n) described above is obviously not a polynomial, it is bounded above by a quadratic polynomial in O(n2)O(n^2)O(n2). > It is very convenient to be able to say that a step function bounded above by a quadratic polynomial in O(n2)O(n^2)O(n2) is, itself, in O(n2)O(n^2)O(n2). So this idea got baked into the definition of Big OOO. > If some function can be *bounded above* by a function in O(n2)O(n^2)O(n2) that function is *also* considered to be in O(n2)O(n^2)O(n2). ([View Highlight](https://read.readwise.io/read/01ga7fda6dhvmsv9f0vnxct474)) > When the length of the array is not a perfect square, the algorithm expands the array length to be the next perfect square, and then runs as if this expanded array were its original input. ([View Highlight](https://read.readwise.io/read/01ga7fdk5ag4xsz57h261c5qjx)) --- Title: f(n) = \left\lceil \frac{n}{4}\right\rceil^2 Author: brilliant.org Tags: TVZ, readwise, articles date: 2023-08-29 --- # f(n) = \left\lceil \frac{n}{4}\right\rceil^2  URL:: https://brilliant.org/courses/computer-science-algorithms/the-speed-of-algorithms-2/more-big-o/3/ Author:: brilliant.org ## Highlights > The picture of Big OOO isn't a bunch of separate buckets: instead, it looks like a nesting doll. All the functions in O(n)O(n)O(n) also appear in O(n2)O(n^2)O(n2). ([View Highlight](https://read.readwise.io/read/01ga7fexj2qbrfbpep87reh89m)) > Although the step function f(n)f(n)f(n) described above is obviously not a polynomial, it is bounded above by a quadratic polynomial in O(n2)O(n^2)O(n2). > It is very convenient to be able to say that a step function bounded above by a quadratic polynomial in O(n2)O(n^2)O(n2) is, itself, in O(n2)O(n^2)O(n2). So this idea got baked into the definition of Big OOO. > If some function can be *bounded above* by a function in O(n2)O(n^2)O(n2) that function is *also* considered to be in O(n2)O(n^2)O(n2). ([View Highlight](https://read.readwise.io/read/01ga7fda6dhvmsv9f0vnxct474)) > When the length of the array is not a perfect square, the algorithm expands the array length to be the next perfect square, and then runs as if this expanded array were its original input. ([View Highlight](https://read.readwise.io/read/01ga7fdk5ag4xsz57h261c5qjx)) --- Title: F(n) = \Left\lceil \Frac{n}{4}\right\rceil^2 Author: brilliant.org Tags: readwise, articles date: 2024-01-30 --- # F(n) = \Left\lceil \Frac{n}{4}\right\rceil^2  URL:: https://brilliant.org/courses/computer-science-algorithms/the-speed-of-algorithms-2/more-big-o/3/ Author:: brilliant.org ## AI-Generated Summary Not all algorithms have a runtime cost that's a nice polynomial function of n. For instance, you might have an array algorithm that runs in k2steps on arrays of length n=4k. ## Highlights > The picture of Big OOO isn't a bunch of separate buckets: instead, it looks like a nesting doll. All the functions in O(n)O(n)O(n) also appear in O(n2)O(n^2)O(n2). ([View Highlight](https://read.readwise.io/read/01ga7fexj2qbrfbpep87reh89m)) > Although the step function f(n)f(n)f(n) described above is obviously not a polynomial, it is bounded above by a quadratic polynomial in O(n2)O(n^2)O(n2). > It is very convenient to be able to say that a step function bounded above by a quadratic polynomial in O(n2)O(n^2)O(n2) is, itself, in O(n2)O(n^2)O(n2). So this idea got baked into the definition of Big OOO. > If some function can be *bounded above* by a function in O(n2)O(n^2)O(n2) that function is *also* considered to be in O(n2)O(n^2)O(n2). ([View Highlight](https://read.readwise.io/read/01ga7fda6dhvmsv9f0vnxct474)) > When the length of the array is not a perfect square, the algorithm expands the array length to be the next perfect square, and then runs as if this expanded array were its original input. ([View Highlight](https://read.readwise.io/read/01ga7fdk5ag4xsz57h261c5qjx)) --- Title: f(n) = \left\lceil \frac{n}{4}\right\rceil^2 Author: brilliant.org Tags: readwise, articles date: 2024-01-30 --- # f(n) = \left\lceil \frac{n}{4}\right\rceil^2  URL:: https://brilliant.org/courses/computer-science-algorithms/the-speed-of-algorithms-2/more-big-o/3/ Author:: brilliant.org ## AI-Generated Summary Not all algorithms have a runtime cost that's a nice polynomial function of n. For instance, you might have an array algorithm that runs in k2steps on arrays of length n=4k. ## Highlights > The picture of Big OOO isn't a bunch of separate buckets: instead, it looks like a nesting doll. All the functions in O(n)O(n)O(n) also appear in O(n2)O(n^2)O(n2). ([View Highlight](https://read.readwise.io/read/01ga7fexj2qbrfbpep87reh89m)) > Although the step function f(n)f(n)f(n) described above is obviously not a polynomial, it is bounded above by a quadratic polynomial in O(n2)O(n^2)O(n2). > It is very convenient to be able to say that a step function bounded above by a quadratic polynomial in O(n2)O(n^2)O(n2) is, itself, in O(n2)O(n^2)O(n2). So this idea got baked into the definition of Big OOO. > If some function can be *bounded above* by a function in O(n2)O(n^2)O(n2) that function is *also* considered to be in O(n2)O(n^2)O(n2). ([View Highlight](https://read.readwise.io/read/01ga7fda6dhvmsv9f0vnxct474)) > When the length of the array is not a perfect square, the algorithm expands the array length to be the next perfect square, and then runs as if this expanded array were its original input. ([View Highlight](https://read.readwise.io/read/01ga7fdk5ag4xsz57h261c5qjx))