BigO running time on some methods

Question

Ok, these are all pretty simple methods, and there are a few of them, so I didnt want to just create multiple questions when they are all the same thing. BigO is my weakness. I just cant figure out how they come up with these answers. Is there anyway you can give me some insight into your thinking for analyzing running times of some of these methods? How do you break it down? How should I think when I see something like these? (specifically the second one, I dont get how thats O(1))

Answer 1

function f1:
  loop 3 times
    loop n times

Therefore O(3*n) which is effectively O(n).

---

function f2:
  loop 50 times

O(50) is effectively O(1).

We know it will loop 50 times because it will go until n = n - (n / 50) is 0. For this to be true, it must iterate 50 times (n - (n / 50)*50 = 0).

---

function f3:
  loop n times
    loop n times

Therefore O(n^2).

---

function f4:
  recurse n times

You know this because worst case is that n = high - low + 1. Disregard the +1. That means that n = high - low.

To terminate,

arr[hi] * arr[low] > 10

Assume that this doesn't occur until low is incremented to the highest it can go (high).

This means n = high - 0 and we must recurse up to n times.

---

function 5:
  loops ceil(log_2(n)) times

We know this because of the m/=2.

For example, let n=10. log_2(10) = 3.3, the ceiling of which is 4.

10 / 2 = 
  5 / 2 = 
   2.5 / 2 = 
    1.25 / 2 = 
      0.75

In total, there are 4 iterations.