This post is part of a personal study group activity, summarizing the content after reading through the book "Grokking Algorithms."

Even for a single problem, there can be countless algorithms that solve it. If a problem can be solved by any method whatsoever, it deserves to be called an algorithm in its own right, but not all algorithms are created equal. That's because of differences in the efficiency with which they solve the problem. Even if two algorithms both ultimately solve the problem, some do so brute-force while others do so remarkably efficiently. And we would generally consider the latter to be more deserving of the name "algorithm."

The notation that expresses the performance of such an algorithm as a single rule is Big O notation. This chapter explains Big O notation for algorithms.

You might think that measuring an algorithm's performance means measuring how long it takes to run, but surprisingly, elapsed time is not an objective performance metric. This is because every computer has different performance. Running the same game, one computer might pull 165 frames on ultra settings, while another might stutter even on the lowest settings. Even performing the same task, the time it takes varies wildly depending on the computer's performance.

That's why the appropriate metric for measuring an algorithm's performance is the number of processing steps. Let's use the read operation and linear search from the previous chapter as examples.

For the read operation, regardless of whether the array has 10 elements or 100 million, only one step is needed to read the element at index i. In contrast, for linear search, the more elements there are, the more steps the operation requires. With $N$ elements in an array, in the worst case—where the element being searched for is at the very end—$N$ steps are required.

In other words, the read operation always requires just one step, so it can be denoted as $O(1)$, while linear search can be denoted as $O(N)$. This notation is called time complexity.

Some operations, like the read operation, require a fixed number of steps regardless of the number of elements, while other operations, like linear search, have a variable number of steps depending on the size of the elements. As mentioned in the previous section, the time complexity of the read operation is $O(1)$, and the time complexity of linear search is $O(N)$. Comparing these on a graph looks like this.

$O(N)$ follows the same pattern as the familiar one-dimensional graph $y = x$. As the number of elements increases by 1, the number of steps also increases proportionally by 1. This pattern is called linear time. However, $O(1)$ follows the same pattern as the constant graph $y = 1$, which stays flat regardless of the number of steps. This pattern is called constant time.

$O(1)$ is a bit peculiar in that all of the graphs below have a time complexity of $O(1)$.

You might think that requiring two steps regardless of the number of elements would be $O(2)$, or that requiring 100 steps would be $O(100)$, but Big O notation doesn't concern itself much with the exact number of steps as long as it stays constant. That is, even if the number of steps were 100 million, the time complexity would still be $O(1)$.

Constant time is generally considered more efficient than linear time. The reason is shown in the graph below.

※ Since $O(1)$'s values are too small to display clearly, they're shown against the secondary axis on the right.

Without thinking too hard about it, a linearly increasing graph will eventually surpass a constant graph. In other words, from the broad perspective of an ever-growing number of elements, linear time will eventually become less efficient than constant time. In the example, once there are more than 10 elements, the efficiency of linear time steadily declines.

Now let's think about the linear time case again. It certainly means that the number of steps can be at most $N$, but it doesn't mean it's always exactly $N$. For example, if you search for 5 in an array of 100 million elements sorted in ascending order starting from 1, only 5 steps are needed. Even so, the book explains that constant time is relatively more efficient than linear time. Why is that? We'll find the answer in the next section.

Depending on the position of the element being searched for, linear search may not take as much time as you'd expect. In the best case, the element is at the very front, so only one step is needed, giving it the same time complexity as $O(1)$. But in the worst case, the element is at the very end, requiring the full $N$ steps, giving it a time complexity of $O(N)$.

Generally, we can't know in advance what data an algorithm will process or how much of it. If we apply the best-case scenario to an arbitrary algorithm with a time complexity of $O(N)$, it will behave close to $O(1)$; if we apply the worst-case scenario, it will behave close to $O(N)$. Algorithms are fundamentally evaluated from the most pessimistic standpoint.

Let's think about ordering something online. Say the item you want is sold at the same price by several vendors, but the delivery time differs. Each vendor's page states the following, and let's assume delivery never falls outside this stated range.

• Vendor A: as fast as today, as slow as a week later
• Vendor B: as fast as tomorrow, as slow as 3 days later
• Vendor C: as fast as 3 days, as slow as 5 days later

If we absolutely need the item within 3 days, Vendor B would be the safest choice. Sure, ordering from Vendor A might get it to us today, but in the worst case we might have to wait a full week, so the risk of exceeding 3 days can't be ignored. If it arrives quickly, that's simply a bonus, but since it must not exceed 3 days, Vendor A isn't appropriate either. Vendor C goes without saying.

Algorithms follow the same reasoning. Suppose there's an $O(N)$ algorithm where $N$ maxes out at 100, and for performance reasons a crash occurs if the number of steps exceeds 50—this algorithm wouldn't be appropriate. Knowing the worst-case scenario like this is how we prepare for failures. For this reason, an algorithm's performance is always expressed based on the worst case.

Of course, time complexity isn't limited to just $O(1)$ and $O(N)$. Take the binary search we covered in Chapter 2—its number of steps does increase with the number of elements, but not linearly like $O(N)$. In other words, it has a time complexity that falls somewhere between $O(1)$ and $O(N)$.

The time complexity of binary search is fundamentally $O(\log_2N)$. The table below shows the number of steps required by $O(1)$, $O(\log_2N)$, and $O(N)$.

※ Since $O(1)$ and $O(\log N)$'s values are too small to display clearly, they're shown against the secondary axis on the right.

The $\log$ we commonly refer to is short for logarithm. If $x^n = y$ holds true, expressing this as a logarithm gives $\log_xy = n$.

For example, $3^2 = 9$ holds true. Expressing this as a logarithm gives $\log_39 = 2$. In this way, logarithms let us find the exponent of a number.

Now that we have some understanding of logarithms from the section above, let's discuss $O(\log N)$. In mathematics, $\log_{10}x$ is typically abbreviated as $\log$, but in Big O notation, it's an abbreviation for $\log_2x$. This is because the decimal system is used in the real world, while computers use the binary system.

Comparing $O(N)$ and $O(\log N)$ looks like this.

$O(N)$ increases proportionally as $N$ increases, but $O(\log N)$ only increases by 1 each time $N$ exactly doubles.

As a side note, the table above alone makes it easy to see why logarithms matter so much in fields like astronomy that deal with astronomically large numbers. $2^{100}$ equals 1,267,650,600,228,229,401,496,703,205,376. That's a figure close to 100 "yang" (quindecillion-scale), a unit that far exceeds even "jo" (trillion), the largest unit of numbers most people encounter.

Units for astronomically large numbers
In general, the largest unit most people encounter meaningfully is "jo" (trillion), a figure reached by multiplying by 100 million a thousand times over.
Beyond "jo," the units continue as "gyeong," "hae," "ja," and "yang," in order—and in real life, discussing magnitudes beyond "gyeong" has little practical meaning.

Unlike everyday life, fields like mathematics and astronomy sometimes deal with numbers so large they'd otherwise be meaningless to us, but expressing them as logarithms lets us handle them effectively.

Let's apply what we've covered so far to actual code. Suppose we have an array with 4 elements and an algorithm that prints out each value in the array one by one.

JAVA
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;

/**
 * 누구나 자료 구조와 알고리즘 빅 오 표기 클래스
 *
 * @author RWB
 * @see <a href="https://blog.itcode.dev/posts/2021/07/14/about-algorithm-chapter03/">빅 오 표기법</a>
 * @since 2021.07.14 Wed 17:40:00
 */
public class BigO
{
	/**
	 * 메인 함수
	 *
	 * @param args: [String[]] 매개변수
	 *
	 * @throws IOException 데이터 입출력 예외
	 */
	public static void main(String[] args) throws IOException
	{
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		// 배열
		String[] things = { "apples", "baboons", "cribs", "delcimers" };
		
		// 배열마다 하나씩 순회
		for (String thing : things)
		{
			StringBuilder builder = new StringBuilder();
			builder.append("Here's a thing: ");
			builder.append(thing);
			
			writer.write(builder.toString());
			writer.newLine();
		}
		
		writer.newLine();
		writer.flush();
		writer.close();
	}
}

The source code is as shown above.

TC
Here's a thing: apples
Here's a thing: baboons
Here's a thing: cribs
Here's a thing: delcimers

The result is as shown above.

It reads each element one by one and prints its content. In other words, as the number of elements grows, the work grows linearly right along with it, so this algorithm's time complexity can be expressed as $O(N)$.

Now let's look at the most basic algorithm that just prints a single string.

JAVA
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;

/**
 * 누구나 자료 구조와 알고리즘 빅 오 표기 클래스
 *
 * @author RWB
 * @see <a href="https://blog.itcode.dev/posts/2021/07/14/about-algorithm-chapter03/">빅 오 표기법</a>
 * @since 2021.07.14 Wed 17:56:49
 */
public class BigO2
{
	/**
	 * 메인 함수
	 *
	 * @param args: [String[]] 매개변수
	 *
	 * @throws IOException 데이터 입출력 예외
	 */
	public static void main(String[] args) throws IOException
	{
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		writer.write("Hello world!");
		writer.newLine();
		writer.flush();
		writer.close();
	}
}

The source code is as shown above.

TC
Hello world!

The result is as shown above.

It might be a stretch to call this an algorithm, but regardless, the number of steps required to perform it is always exactly one. In other words, its time complexity is $O(1)$.

Let's look at a more substantial example.

JAVA
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

/**
 * 누구나 자료 구조와 알고리즘 소수 판별 클래스
 *
 * @author RWB
 * @see <a href="https://blog.itcode.dev/posts/2021/07/14/about-algorithm-chapter03/">빅 오 표기법</a>
 * @since 2021.07.14 Wed 18:01:20
 */
public class CheckPrime
{
	/**
	 * 메인 함수
	 *
	 * @param args: [String[]] 매개변수
	 *
	 * @throws IOException 데이터 입출력 예외
	 */
	public static void main(String[] args) throws IOException
	{
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		writer.write("소수를 판별할 값 입력 >> ");
		writer.flush();
		
		// 입력값
		int target = Integer.parseInt(reader.readLine());
		
		// 소수일 경우
		if (isPrime(target))
		{
			writer.write("소수로 판별됨");
		}
		
		// 아닐 경우
		else
		{
			writer.write("소수가 아닌 것으로 판별됨");
		}
		
		writer.newLine();
		writer.flush();
		
		writer.close();
		reader.close();
	}
	
	/**
	 * 소수 여부 반환 함수
	 *
	 * @param num: [int] 대상 값
	 *
	 * @return [boolean] 소수 여부
	 */
	private static boolean isPrime(int num)
	{
		for (int i = 2; i < num; i++)
		{
			// 나누어 떨어지는 수가 있을 경우
			if (num % i == 0)
			{
				return false;
			}
		}
		
		return true;
	}
}

The source code is as shown above.

• Input value

TC
156842101

• Output value

TC
소수가 아닌 것으로 판별됨

This code is an algorithm that takes an arbitrary value as input and determines whether it's prime. Using this algorithm, we can easily see that 156842101 is not prime.

This algorithm is a very basic one that determines primality by dividing target by each value from the smallest prime, 2, up to target, checking whether it divides evenly.

The worst case occurs when the value being checked is itself prime, requiring the full range of work from 2 to target - 1, for a total of target - 2 operations. When $N = target$, the -2 isn't a particularly meaningful value, so it's fine to consider this algorithm's time complexity to be $O(N)$.

Since I never formally studied algorithms, I never properly understood time complexity concepts like Big O notation. This was a truly meaningful chapter for understanding the concept of time complexity and how it's calculated.

The next chapter explains how to use this Big O notation to improve algorithms.