Time Complexity


Example 1

   x = n
   while ( x > 0 ) {
       x = x - 1
   }

The above is 𝑂(𝑛)$O(n)$

Example 2

   x = n
   while ( x > 0 ) {
       x = x / 2
   }

The above is 𝑂(log𝑛)$O(\log n)$

Example 3

   x = n
   while ( x > 0 ) {
      y = n
      while ( y > 0 ) {
          y = y - 1
      }
      x = x - 1
   }

The above is 𝑂(𝑛2)$O(n^2)$

Example 4

   x = n
   while ( x > 0 ) {
      y = x
      while ( y > 0 ) {
          y = y - 1
      }
      x = x - 1
   }

The above is 𝑂(𝑛2)$O(n^2)$

Example 5

   x = n
   while ( x > 0 ) {
      y = n
      while ( y > 0 ) {
          y = y / 2
      }
      x = x - 1
   }

The above is 𝑂(𝑛log𝑛)$O(n\log n)$

Example 6

   x = n
   while ( x > 0 ) {
      y = x
      while ( y > 0 ) {
          y = y / 2
      }
      x = x - 1
   }

The above is 𝑂(𝑛log𝑛)$O(n\log n)$

Example 7

   x = n
   while ( x > 0 ) {
      y = n
      while ( y > 0 ) {
          y = y - 1
      }
      x = x / 2
   }

The above is 𝑂(𝑛log𝑛)$O(n\log n)$

Example 8

   x = n
   while ( x > 0 ) {
      y = x
      while ( y > 0 ) {
          y = y - 1
      }
      x = x / 2
   }

The above is 𝑂(𝑛)$O(n)$

Example 9

   x = n
   while ( x > 0 ) {
      y = n
      while ( y > 0 ) {
          y = y / 2
      }
      x = x / 2
   }

The above is 𝑂(log2𝑛)$O({\log }^{2}n)$

Example 10

   x = n
   while ( x > 0 ) {
      y = x
      while ( y > 0 ) {
          y = y / 2
      }
      x = x / 2
   }

The above is 𝑂(log2𝑛)