Week #10

Thoughts:

Big-Oh, Big-Omega, Big-Theta...


This week we talked about concepts of Big-Oh, Big-Omega and Big-Theta and introduced some proofs of them. And here I summarized the strategy of writing a proof.

1.How to write a proof:

Step 1:
Write down the proof structure, leave the value of c and B blank.

Pick c = ______ , then c \in R+
Pick B = ______ , then B \in N
Assume n >= B



Conclude n >= B => f(n) <= cg(n)   # this is big-Oh, if it's big-Omega then flip the inequality
Conclude exists c ...


Step 2
Make every element in the polynomial to the same with the largest power in the polynomial. Find the value of B.

Then f(n)  = 5n3 + 4n2 + 2n  + 1
          <= 5n3 + 4n3 + 2n3 + n3    # B >= 1


Step 3
Merge all the terms, find the value of c

... = 12n3
    = cn3    # c = 12
    = cg(n)

Step 4
Complete the proof

2. Meaning of Big-Oh, Big-Omega and Big-Theta.

There do not exists a method to precisely predict the time an algorithm will take. It heavily depends on the hardware and input. The only way to know the time of the algorithm takes is to actually run the program on the machine and measure the time. But in some cases for example the programis extremely complicated, or for example in the scenario that a programmer is trying to determine between two algorithms. However, time complexity provide us a method to compare two different algorithms. So we can know directly what kind of sorting algorithm we should use for this intput, what kind of algorithm of data processing for that input. Time complexity is a powerful tool for computer scientist to maximum their efficiency.