Calculating Time Complexity

Motivation: Efficiency Issues During Programmers Coding Tests

While solving one algorithm problem a day on Programmers, I encountered an efficiency issue even though my answer was correct.

When I looked into the problem, I found an explanation of time complexity stating that the max and min functions take O(n) time.

Up to Level 1, it was enough to get the answer right, but starting from Level 2, efficiency issues also had to be considered.

Time Complexity

Time complexity is used when analyzing the execution time of an algorithm. Since execution time is measured differently depending on the execution environment, execution time is evaluated by the number of executions of basic operations.

Basic Operations

1. Data input/output - copy, move…

2. Arithmetic operations - add, multiply …

3. Control operations - if, while …

• O (Big-O): Worst-case time complexity
• Ω (Omega): Best-case time complexity
• Θ (Theta): Average-case time complexity

When answering the question, “What is the time complexity of this code?”, which we commonly ask, we are referring to time complexity expressed using Big-O notation.

**Because Big-O notation considers the worst case, it allows us to think in advance about the longest possible time during the program’s execution. **

• Assume only the worst-case situation
  • Do not assume the best-case situation (Big-Omega), where, luckily, numbers that are easy to calculate mentally appear.
  • Do not calculate what the average situation (Big-Theta) is, because it is not easy to define the ‘average situation’ for multiplication.
• The fewer operations there are, the more efficient the algorithm is considered to be. Other variables (such as hardware performance) are ignored. The number of operations is also not counted exactly, but roughly estimated.

It should not be forgotten that time complexity is calculated ‘approximately’ rather than ‘exactly’. Numerous factors that affect the performance of actual software (hardware performance, proper use of the memory hierarchy, whether caching is used, etc.) are all ignored. This is not because they are unimportant, but because they are difficult to calculate.

[Reference Link] (https://velog.io/@skynet/%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84%EB%8A%94-%EB%AC%B4%EC%97%87%EC%9D%B4%EA%B3%A0-%EC%99%9C-%EC%A4%91%EC%9A%94%ED%95%A0%EA%B9%8C)

Let’s Calculate Time Complexity

Criteria for Counting Operations

• Assignment
• Four arithmetic operations

Let’s calculate!

O(1)

// 1번 코드
int sum = (x+1)*x/2;

In the case of code 2, ‘(x+1)’ is calculated once, ‘*x’ once, and ‘/2’ once, and the result is assigned to sum once, for a total of four operations. However, in Big-O notation, this becomes O(1).

O(1)

// 2번 코드
int sum = 0;
for(int i = 0; i<n; i++){
	sum+=i;
}

In code 1, ‘sum=0’ is performed once, ‘int i = 0’ once, ‘i++’ n times, and ‘sum+=i’ n times, for a total of 2n+2 operations. In Big-O notation, only the highest-order term is written without its coefficient, so this becomes O(1).

O(n²)

// 3번 코드
int sum = 0;
for(int i = 0; i<n; i++){
	for(int j = 0; j<i;j++){
    	sum+=j;
    }
}

The outer loop in code 3 repeats n times, while the inner loop repeats according to the value of i. i changes from 0 to n-1, and since the inner loop repeats the corresponding number of times for each i, it repeats 0+1+2+…+(n-1) = n*(n-1)/2 times (the sum formula for an arithmetic sequence). If only the highest-order term is written without its coefficient, this also becomes O(n²).

O(N)

// 4번 코드
int sum = 0;
for(int i = n; i>0; i/=2){
	for(int j = 0; j<i; j++){
    	sum+=j;
    }
}

In code 4, the outer loop repeats logN times, while the number of repetitions of the inner loop varies according to the value of i. (💡 The reason it repeats logN times is that i/=2.) i changes from n to 1, and since the inner loop repeats the corresponding number of times for each i, it repeats n+(n/2)+(n/4)+..+1 = 2n times, making it O(N).

Why Consider Time Complexity

Time complexity was created to determine which method (algorithm) is more efficient among various solutions.

ex) There are two algorithms for looking up one person among the 50 million people in Korea.

Algorithm A: O(log n)

Algorithm B: O(n^2)

->Algorithm A performs 25 operations, while Algorithm B performs 2500000000000000 operations.

->Algorithm A takes less than 1 second.

->Algorithm B takes about 120 days..

Even so, we always make an effort to reduce time complexity so that we do not waste the valuable resource of time.

This effort is called optimization.

Tip

Additionally, I would like to introduce a way to roughly estimate time complexity when solving algorithm problems. (This article is written for those who have just started solving Baekjoon and swea problems! Please use it as a reference haha)

Here, a time limit of 1 second means that when my code is executed, its execution time must be within 1 second.

Since in most environments, 100 million operations take about 1 second,

this means that even when running the largest test case on my code, it must pass only if the number of operations is within 100 million.

Therefore, before solving a problem, it is a good idea to check the time limit and the amount of input data, plan what time complexity the code should have, and then start coding.

The link below explains well how to use time complexity in problems. Tip Link

Tip Summary

1. Check the time limit and the maximum size of the input data, and consider the time complexity of the code I need to write.
2. Code accordingly
3. Enter the largest test case.
4. Get a feel for the output time or measure it using profiling features or add <time.h> and print the time

[References] (https://velog.io/@thd0427/%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84-%EA%B5%AC%ED%95%98%EB%8A%94-%EB%B2%95)

How to Pass the Efficiency Check

1. Runtime Error

• Reduce the use of recursive functions
• Reduce the number of parameters of built-in functions (stack size exceeded)

2. Time Limit Exceeded

• Check the execution time of the built-in functions used, then replace them with another method
• Algorithm problems

Conclusion: Write a new algorithm

Legendary explanation by Nomad Coders: https://www.youtube.com/watch?v=BEVnxbxBqi8

Source of the Doctor Strange photo: https://www.4flix.co.kr/board/free/66520?sfl=mb_id%2C1&stx=admin&sst=wr_good&sod=asc&sop=and&page=240