Big-O analysis for a loop

Question

I've got to analyze this loop, among others, and determine its running time using Big-O notation.

for ( int i = 0; i < n; i += 4 )
    for ( int j = 0; j < n; j++ )
        for ( int k = 1; k < j*j; k *= 2 )`

Here's what I have so far:

for ( int i = 0; i < n; i += 4 ) = n

---

for ( int j = 0; j < n; j++ ) = n

---

for ( int k = 1; k < j*j; k *= 2 ) = log^2 n

Now the problem I'm coming to is the final running time of the loop. My best guess is O(n^2), however I am uncertain if this correct. Can anyone help?

Edit: sorry about the Oh -> O thing. My textbook uses "Big-Oh"

Answer 1

First note that the outer loop is independent from the remaining two - it simply adds a (n/4)* multiplier. We will consider that later.

Now let's consider the complexity of

for ( int j = 0; j < n; j++ )
    for ( int k = 1; k < j*j; k *= 2 )

We have the following sum:

0 + log₂(1) + log₂(2 * 2) + ... + log₂(n*n)

It is good to note that log₂(n^2) = 2 * log₂(n). Thus we re-factor the sum to:

2 * (0 + log₂(1) + log₂(2) + ... + log₂(n))

It is not very easy to analyze this sum but take a look at this post. Using Sterling's approximation one can that it is belongs to O(n*log(n)). Thus the overall complexity is O((n/4)*2*n*log(n))= O(n^2*log(n))

Answer 2

• In terms of j, the inner loop is O(log_2(j^2)) time, but sine log_2(j^2)=2log(j), it is actually O(log(j)).

• For each iteration of middle loop, it takes O(log(j)) time (to do the inner loop), so we need to sum:

  sum { log(j) | j=1,..., n-1 } log(1) + log(2) + ... + log(n-1) = log((n-1)!)

And since log((n-1)!) is in O((n-1)log(n-1)) = O(nlogn), we can conclude middle middle loop takes O(nlogn) operations .

• Note that both middle and inner loop are independent of i, so to get the total complexity, we can just multiply n/4 (number of repeats of outer loop) with complexity of middle loop, and get:

  O(n/4 * nlogn) = O(n^2logn)

So, total complexity of this code is O(n^2 * log(n))

Answer 3

Time Complexity of a loop is considered as O(n) if the loop variables is incremented / decremented by a constant amount (which is c in examples below):

   for (int i = 1; i <= n; i += c) {  
        // some O(1) expressions
   }

   for (int i = n; i > 0; i -= c) {
        // some O(1) expressions
   }

Time complexity of nested loops is equal to the number of times the innermost statement is executed. For example the following sample loops have O(n²) time complexity:

for (int i = 1; i <=n; i += c) {
       for (int j = 1; j <=n; j += c) {
          // some O(1) expressions
       }
   }

   for (int i = n; i > 0; i += c) {
       for (int j = i+1; j <=n; j += c) {
          // some O(1) expressions
   }

Time Complexity of a loop is considered as O(logn) if the loop variables is divided / multiplied by a constant amount:

for (int i = 1; i <=n; i *= c) {
       // some O(1) expressions
   }
   for (int i = n; i > 0; i /= c) {
       // some O(1) expressions
   }

Now we have:

for ( int i = 0; i < n; i += 4 ) <----- runs n times
    for ( int j = 0; j < n; j++ ) <----- for every i again runs n times
        for ( int k = 1; k < j*j; k *= 2 )` <--- now for every j it runs logarithmic times.

So complexity is O(n²logm) where m is n² which can be simplified to O(n²logn) because n²logm = n²logn² = n² * 2logn ~ n²logn.