My Understanding of Big O Notation

Yeah, an interview test is the main reason I decided to look at data structure and algorithms that lead to this topic "My Understanding of Big O Notation"

Why do I choose to study Big O Notation? Well, based on the research I've done, let say I've two implementation / two algorithms for the same codes.

How do you know which one is better? Big O will give us a framework for officially defining which code is better.

Why is Big O important? When you're dealing with petabytes of data efficiency matters. Big O helps you when making a trade-off between space and time.

Example of Big O Notation:

example 1.

nums = [1,2,3,4,5]
n = len(nums)
sum = 0
for i in range(0,n):
    sum += nums[i]
print("sum of arrays: ", sum)

example 2.

nums = [1,2,3,4]
n = len(nums)
print("sum of arrays: " n * (n + 1) /2)

Now, let's discuss. What makes an algorithm better than the other?

1. Takes less time
2. Takes less space

Big O is used to formalize the notion that two functions "grow at the same rate," or one function "grows faster than the other," and such. Informally, saying some equation f(n) = O(g(n)) means it is less than some constant multiple of g(n). The notation is read, "f of n is big oh of g of n".

There're options to how runtime grows with the input.

1. Linear f(N) = f(N) = N
2. Quadratic f(N) = f(N) = N
3. constant f(N) = f(N) = N

okay, I'll let try and explain these options

Constant complexity 0(1):

In constant algorithms, the number of operations that our algorithm takes doesn't change as our input grows.

example:

def sumUpN(n):
    return n * (n + 1) / 2
result = sumUpN(4)
print(result)

Linear complexity O(N):

Each linear-complexity needed, increase linearly with our input. As our input grows the number of operations grows.

def sumUpToN(n):
    sum = 0
    for i in range(0, n + 1):
        sum += i
    return sum
result = sumUpToN(4)

"N" could be anything. As "N" increases, the number of operations increases. The number of operations is bounded by multiple of "N" (10n,20n, etc)

Even these two algorithms do the same thing:

## constant algorithm.
def sumUpN(n):
    return n * (n + 1) / 2
result = sumUpN(4)
print(result)

## linear algorithm.
def sumUpToN(n):
    sum = 0
    for i in range(0, n + 1):
        sum += i
    return sum
result = sumUpToN(4)
print(result)

but the way the result is calculated in each of them is different. "N" duration changes in performance as "N" grows.

For the constant algorithm O(1). it won't matter what we input. it'll always do the same number of operations.

For the linear algorithm O(N): It does matter what we input, because as our input increases, our number of operations increases, so as our runtime increases.

example 2 of a linear algorithm:

def printTwice(n)
    for i in range(0,n):
        print("first loop", i)
    for j in range(n,0,-1):
        print("second loop", i)

The first one will print the element starting from 0 to N. The second one will print the element starting from "N" to 0

Polynomial algorithm 0(N):

example:

def quadratic(n):
    for i in range(0,n):
        for j in range(0,n):
            print("This is quadratic")

The first loop goes for "N" times. The inner loop goes "N" times for each iteration in the outer loop. complexity: 0(N*N) = 0(N^2)

That means as our input grows, our runtime grows at the rate of "N^2". The relation of a polynomial algorithm is not as smooth as a linear algorithm, because our runtime grows faster than the linear algorithm, because it grows quadratically.

Big O Simplification

nums = [1,2,3,4]
n = len(nums)
sum = 0 
for i in range(o,n):
    sum += nums[i]
print("sum of arrays: " sum)

simplification

first assignment is the "nums" array (nums = [1,2,3,4]). the second assignment is the "n" to find the length of the nums array (n = len(nums)) third assignment is the sum "sum = 0" we also have our loop "for i in range(o,n)" . For this, to work we can count three N operations for the loop decoration alone.

To create a loop that means we've got:

• "N assignment" for the "i" variable
• addition because we increament "i" for each pass
• "N" comparison, beacuse we need to verify what check we should continue the loop is still on

inside our loop, we've two "N": "sum += nums[i]" In addition, because this addition will have "N" time since it's in a loop. And finally an assignment.

so, the number of operations we've here is O(5N+3)

Note:

the first rule of simplification is that we ignore constants. So, if we have complexity that follows this formula O(aN+b) = O(N). where "a & b" are constants. We ignore "a & b", we'll just say that the complexity is Big O of N "O(N)"

That ignores constant rule is the reason we say that constant complexity is equivalent to Big O of 1 "O(1)". It doesn't matter if the constant is 500 or 1000, it's still a constant. O(500) = O(1). That's also the reason we don't say 5N^2 = O(N^2)

Ignore smaller terms.

consider this formula:

5N^2 + 3N + 1

How do we represent this formula in terms of Big O?

The complexity here is not O(N^2 + N). it's O(N^2).

The reason for this is really simple. "N" is a smaller term than "N^2". Like constant, we ignore smaller terms, that is because the impact "N^2" will have or the function of the runtime will be so great that adding "N" to it doesn't make a difference.

Note:

a. Arithmetic operations, assignments are constants

b. Direct array element access (by index) is a constant

example 1.

def newPrint(n):
    for i in range(o,n):
        for j in range(o,n):
            print("first loop")

        for z in ranfe (o, n):
            print("second loop")

what's the complexity?

ans: O(N^2)

We have a loop that contains two nested loops. Each loop will run "N" times, which means both of them will run 2 "N" times. which means our complexity is: "O(2 * N^2)" since we agreed to ignore constant, the final complexity is O(N^2)

Big O space complexity How much additional memory do we consume to run the algorithm? When analyzing space complexity, we only care about the space our algorithm takes. We don't include the space taken up by the input.

example:

def sumUpToN(arr):
    sum = 0
    n = len(arr)
    for i in range(0,n):
        sum += arr[i]

We've three variables.

• sum = 0
• n = len(arr)
• for i in range(0,n)

The "i" in the loop gets assigned "N" times, but it's a single variable, it doesn't matter how many operation that was done on it. The time complexity is the number of operations, but we're concerning ourselves with the space complexity only.

what is the space complexity of the example above? This's Big O of 1 "O(1)" because we don't have any extra memory saved that has a relationship with "N" in any way.

space complexity of popular data structures.

• Hash tables : O(N) dictionaries, hash maps. They're space complexity of Big O of N. They're linear, that because the number of the slot in hash maps increases linearly with the value of "N"

• same with: (a): stacks: O(N) - (b): strings: O(N) - (c): arrays: O(N) - (d): Queues: O(N)