Big O Notation

Question 1

What is Big O Notation?

Answer 1

An expression used to express runtime by the measurement of how quickly the runtime grows relative to the input, as the input gets arbitrarily large.
We’re usually talking about the “worst case”.

Question 2

What is Big O Notation?

Answer 2

A measurement of how the runtime and space complexity grows over input. Sometimes called Asymptotic Analysis.

Question 3

Other Names for Big O Notation?

Answer 3

Asymptotic Analysis.
asymptotic analysis, also known as Asymptotics, supposes that we are interested in the properties of a function f (n) as n becomes very large. If f(n) = n^2 + 3n, then as n becomes very large, the term 3n becomes insignificant compared to n^2.
https://en.wikipedia.org/wiki/Asymptotic_analysis

Question 4

List some of Big O Time Complexity?

Answer 4

1. O(1) time (or “constant time”)
2. O(n) time (or “linear time”)
3. O(n^2) time (or “quadratic time”)
4. O(n^3) time (or Cubic)
5. O(2^n) time (or Exponential)
6. O(n!) time (or Factorial)
7. O(log n) time (or Logarithmic)
8. O(n log n) time (or Linearithmic)

Question 5

What is the complexity of the following?
1. O(2n + 4)
2. O(n^2 + n)
3. O(1+n/2+100)
4. O(n + n^2)
5. O(n^2 / 2 + 100n)
6. O(n^3 +50n^2 +10000)
7. O((n+30)∗(n+5))

Answer 5

1. O(n)
2. O(n^2)
3. O(n)
4. O(n^2)
5. O(n^2)
6. O(n^3)
7. O(n^2)

Question 6

What is Space Complexity?

Answer 6

Sometimes we want to optimize for using less memory instead of (or in addition to) using less time. Talking about memory cost (or “space complexity”) is very similar to talking about time cost. We simply look at the total size (relative to the size of the input) of any new variables we’re allocating.

Question 6

What is Space Complexity?

Answer 6

Sometimes we want to optimize for using less memory instead of (or in addition to) using less time. Talking about memory cost (or “space complexity”) is very similar to talking about time cost. We simply look at the total size (relative to the size of the input) of any new variables we’re allocating.

Question 6

What is Space Complexity?

Answer 6

Sometimes we want to optimize for using less memory instead of (or in addition to) using less time. Talking about memory cost (or “space complexity”) is very similar to talking about time cost. We simply look at the total size (relative to the size of the input) of any new variables we’re allocating.

Question 7

What is not considered in Space Complexity?

Answer 7

The input is not added and considered in space complexity.
Usually, when we talk about space complexity, we’re talking about additional space, so we don’t include space taken up by the inputs. For example, this function takes constant space even though the input has n items: