Question

Hi,

can someone please explain to me the time complexity of an algorithm specially big O analysis with some clear examples.

the language I am studying is Java.

thanks

Answer 1

`Hey,

Note: Brother in case of any queries, just comment in box I would be very happy to assist all your queries

Big-O Notation

We express complexity using big-O notation. For a problem of size N:

• a constant-time method is "order 1": O(1)
• a linear-time method is "order N": O(N)
• a quadratic-time method is "order N squared": O(N²)

Note that the big-O expressions do not have constants or low-order terms. This is because, when N gets large enough, constants and low-order terms don't matter (a constant-time method will be faster than a linear-time method, which will be faster than a quadratic-time method). See below for an example.

Formal definition:

• A function T(N) is O(F(N)) if for some constant c and for all values of N greater than some value n₀:

  T(N) <= c * F(N)

The idea is that T(N) is the exact complexity of a method or algorithm as a function of the problem size N, and that F(N) is an upper-bound on that complexity (i.e., the actual time/space or whatever for a problem of size N will be no worse than F(N)). In practice, we want the smallest F(N) -- the least upper bound on the actual complexity.

For example, consider T(N) = 3 * N² + 5. We can show that T(N) is O(N²) by choosing c = 4 and n₀ = 2. This is because for all values of N greater than 2:

3 * N² + 5 <= 4 * N²

T(N) is not O(N), because whatever constant c and value n₀ you choose, I can always find a value of N greater than n₀ so that 3 * N² + 5 is greater than c * N.

How to Determine Complexities

In general, how can you determine the running time of a piece of code? The answer is that it depends on what kinds of statements are used.

Sequence of statements

• statement 1;
  statement 2;
    ...
  statement k;
  

  (Note: this is code that really is exactly k statements; this is not an unrolled loop like the N calls to add shown above.) The total time is found by adding the times for all statements:

  total time = time(statement 1) + time(statement 2) + ... + time(statement k)

  If each statement is "simple" (only involves basic operations) then the time for each statement is constant and the total time is also constant: O(1). In the following examples, assume the statements are simple unless noted otherwise.
• if-then-else statements

  if (condition) {
      sequence of statements 1
  }
  else {
      sequence of statements 2
  }
  

  Here, either sequence 1 will execute, or sequence 2 will execute. Therefore, the worst-case time is the slowest of the two possibilities: max(time(sequence 1), time(sequence 2)). For example, if sequence 1 is O(N) and sequence 2 is O(1) the worst-case time for the whole if-then-else statement would be O(N).
• for loops

  for (i = 0; i < N; i++) {
      sequence of statements
  }
  

  The loop executes N times, so the sequence of statements also executes N times. Since we assume the statements are O(1), the total time for the for loop is N * O(1), which is O(N) overall.
• Nested loops

  First we'll consider loops where the number of iterations of the inner loop is independent of the value of the outer loop's index. For example:

  for (i = 0; i < N; i++) {
      for (j = 0; j < M; j++) {
          sequence of statements
      }
  }
  

  The outer loop executes N times. Every time the outer loop executes, the inner loop executes M times. As a result, the statements in the inner loop execute a total of N * M times. Thus, the complexity is O(N * M). In a common special case where the stopping condition of the inner loop is j < N instead of j < M (i.e., the inner loop also executes N times), the total complexity for the two loops is O(N²).

Kindly revert for any queries

Thanks.