Preferences

Code Theme

solarized light

login

Time and Space Complexity - Continued

Approximate sizes

In the previous lesson we simplified O(n + 4) to O(n). Why did we do this? If one part of a program takes linear time and another takes constant time, as the size of the variable grows, the time spent performing any operation on the variable term will take a proportionately longer time than anything with a constant. Image n equals one million. one million plus four is indistinguishable from one million; thus the larger term consumes the smaller. Thus giving us a complexity of O(n).

Now how about O(3n)? Lets say n is one thousand. In this case the total complexity would be three thousand. This is definitely larger than before. But what if n is one million? Then the total complexity again is three million. Comparing the two, we see the first value for n is magnitudes smaller than the latter. This tells us the most important part is the power of the term.

Larger complexities

Let's compute a few more complexities.

  • O(n log n + n + 55) ~= O(n log n)
  • O(n^2 + 50000n) ~= O(n^2)
  • O(3^n + n^3) ~= O(3^n)

In every case, big O notation retains the term with the largest power.

One function calls another

What should we do when one function calls another? How can we calculate the total complexity of the original function? We can calculate the complexity of the called function and take it's worst case time and space complexities, then substitute them in where it's called in the original function.

Another example

Let's look at a more complex program. In this example we will look at a simple grid search. The objective of find_abundant_grid is to find the grid that has the most of some target. We use a helper function grid_search to iterate through the grid and count how many match the target.

  1. Variable assignment. Time: O(1) Space: O(1).
  2. Iterate through an array. Time: O(x) Space: O(1).
  3. Variable assigment and max are both constants. Since a function is called, we need to step into it to compute it's complexities to see how it may affect complexities of our program.
  4. Length and width of a grid. Time: O(1) Space: O(1).
  5. Variable assignment. Time: O(1) Space: O(1).
  6. Iteration. Time: O(n) Space: O(1).
  7. Iteration. Time: O(m) Space: O(1).
  8. Conditional. Time: O(1) Space: O(1).
  9. Addition. Time: O(1) Space: O(1).
  10. Return statement. Time: O(1) Space: O(1).
  11. As explained below, grid_search has quadratic time complexity. Time: O(m*n) Space: O(1).
  12. Return statement. Time: O(1) Space: O(1).

Let's calculate the complexity of grid_search first.

Time: O(1+ 1 + m * n * 1 * 1 + 1) = O(m*n + 3) ~= O(m*n)

Space: O(1)

With this we can substitute in these complexities when it's called in the main program.

Time: O(1+ x * (1 + 1 + m*n) + 1) = O(2 + x*m*n + 2x) ~= O(x*m*n) ~= O(n^3)

Space: O(1)

One final note. Because we don't know which term might be the largest, we can make a further simplification by using a single term in the notation, so that we can see the program has cubic time complexity.

Summary

Analyzing time complexity helps identify algorithms that are more efficient for large input sizes and helps make informed decisions when selecting algorithms for specific tasks.

Analyzing space complexity helps ensure efficient memory utilization and allows for optimization and trade-offs between time and space requirements.

Both time complexity and space complexity are crucial considerations in algorithm design and analysis, as they help determine the scalability, efficiency, and resource usage of algorithms in different scenarios.

Practice question

What are the time and space complexities of the following program?

score: 0%