From programming to mathematics

Question

I'm studying algorithms design and analysis, but there is a code that I can't understand.

I know that:

Let $\mathcal P$ be the main program, and $\mathcal P \in O\left(\varphi(n)\right)$ with $\varphi(n)=\max(\varphi_1(n),...,\varphi_k(n))$, $\varphi_i(n)$ is the big-O notation of some sentence and $k$ as the quantity of sentences in the program.

So, by definition, if I have a while loop and I have to evaluate the time in the big-O notation, then I have that:

$\varphi_{while}(n)=\phi_{conditions}+\sum_{i=1}^{n}(\phi_{body}+\phi_{conditions})$ where $\phi$ is the max $O(n)$ of that loop, i.e., $\phi_{body}$ is the max $O(n)$ inside the while loop, and $\phi_{conditions}$ is the max $O(n)$ of the while conditions.

So, this is the code:

int Count (int n, int m){ 

  int j, sentenceCounter = 0, i = 1; 

  while (i <= m) { 
    j = n; 
    while (j != 0){ 
      j = j / 2; 
      sentenceCounter ++; 

    } 
    i++;  
  } 
  return sentenceCounter; 
}

So, my question is:

It is true that $\varphi_{while}=O(1) + \sum_{i=1}^{m}\left( O(1) + \sum_{j=n}^{k}O(1) \right)$ where $k$ is the times of turns in the loop until $j\not=0$?

If not, can you tell me another way to do this?

Thanks!

Answer 1

Eye-balling the code, we see that the outer while-loop is linear. It goes from $i$ to $m$, incrementing by $1$, taking $(m-i)$ steps. The inner while loop is $O(log(n))$ (ie., $k = \lceil log_{2}(n) \rceil + n$). When you see a division-based modification on your counter, that usually suggests log(n). So now you multiply since there are nested loops- $n * log(n) = O(n log(n))$.

Really, for your second series, I would go from $\sum_{i=0}^{\lceil log_{2}(n) \rceil}$ just to make the offsets easier to deal with.