week 8

After the tutorial, I had some idea of big-oh notation. We had same proofs in the lectures as last week, but for this time, I can understand the steps of professor took in the lectures. I started to know the steps taking in while loops and the constant steps.

In IS, the constant steps is step 1 and there are two while loops. Then we need to estimate the maximum steps would take for IS.

And the definition of big-oh notation is: f(n) = O(g(n)) means there are positive constants c and k, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ k. The values of c and k must be fixed for the function f and must not depend on n.