Revised Definition – Time Complexity

Definition – Time Complexity

Introduction

This assignment is to define the term ‘time complexity’ in Computer Science for the public from non-STEM (Science, Technology, Engineering, and Mathematics) fields with rudimentary mathematical knowledge. The goal is to help the target audience understand the meaning and the usage of the technical term. Beginning from simpler definitions, this article expands the definition of the term with examples and usage of time complexity.

Parenthetical Definition

The fact that the time complexity (also called the estimated number of elementary operations) of the new algorithm decreased from O(n) to O(1) clearly tells us how faster it is compared to the previous one.

Sentence Definition

Time complexity is the amount of computation required for an algorithm in terms of the size of data being processed by it. The term is often used to measure how effective an algorithm is in Computer Science (Team GL., 2020).

Expanded Definition

• What is Time complexity?
  Time complexity is the amount of time taken by an algorithm( a finite sequence of well-defined instructions) to run, in terms of the length of the input. It measures the time taken to execute each statement of code in an algorithm (Team GL., 2020). This measurement does not tell people how complicated an algorithm is, but time complexity measures how the number of operations of the algorithm changes as the number of the input increases or decreases. Often, time complexity deals with the case where the size of input infinitely increases and this is why it is also referred to as ‘limiting behavior'(Epp, Susanna S., 2019).
• How to determine the time complexity of an algorithm
  One can determine the time complexity of an algorithm in the following steps (Mejia A, 2020).

1. 1. Understand how the algorithm works
   2. Figure out how many steps are required to finish the algorithm
   3. See how the number of steps changes with different data size
   4. Express the number of steps in a mathematical expression
   5. Use the dominant(the most fast-growing) term in the expression as the time complexity

• Example of time complexity
  Time complexity can be understood more easily with a simple real-life example. Let’s say you work at the front desk of a conference just like Fig.1 below. The number of attendees can be 1, 100, or countlessly many. Now, compare three instructions for gatekeepers, especially the amount of work they have to do as the number of visitors increases.
  

  Fig.1 People are lined up to check-in

  (Source:https://biv.com/article/2019/09/guests-frustrated-corporate-event-runs-smoothly-hyatt-workers-strike)

  • Instruction A:
    (for each attendee)
    a. You greet the attendee
    b. You tell the attendee the basic information about the conference
    c. Repeat a. and b. only for the first 15 visitors assuming that the rest of the attendees will get the required information from the first 15 attendees.In this instruction, you have to take exactly 2 steps for each visitor, and the entire number of steps you have to go increases as more visitors attend the conference. However, it increases only up until the number of visitors is 15.  The important part here is it is not affected by the number of visitors after a certain number of visitors! This type of algorithm, that its amount of computation is not affected as the size of the input(number of visitors in this case) grows has a constant time complexity and is denoted as O(1).
  • Instruction B:
    (for each attendee)
    a. You greet the attendee.
    b. You tell the attendee the basic information about the conference.
    c. Repeat a. and b. for every visitor that attends the conference.This instruction is very similar to the previous one, except that now you have to repeat the 2 steps(Step a. and Step b.) as many as the number of visitors. As the number of visitors becomes 1, 10, 100, and so on, the number of steps you have to take goes 2, 20, 200, and so on. You can tell that the number of total steps is double the number of visitors. So, if the number of visitors is n, then the number of steps you have to go will be 2n.In this type of algorithm that its total number of steps is some fixed number times the size of data has linear time complexity and is denoted as O(n). You can visually understand the different number of operations between O(n) and O(1) by looking at the graph below(Fig. 2). The graph will be explained in more detail below.
    

    Fig.2 Growing Behaviors of Different Time Complexities

    (Source: https://towardsdatascience.com/essential-programming-time-complexity-a95bb2608cac)

  • Instruction C:
    (for each attendee)
    a. You greet the attendee.
    b. You tell the attendee the basic information about the conference.
    c. You tell the attendee all the names of people who are in the conference room now.
    d. Repeat a. and c. for every visitor that attends the conference.In this instruction, step C adds a significant number of steps you have to take as the number of visitors increases. For the first visit, you have to do nothing in step C because there is no previous visitor. For the second visit, you tell the previous visitor’s name. For the third visitor, you have to tell two people’s names which adds up to a total of 3(= 1 + 2) extra steps. In this way, if there are 10 visitors, you have to take 45 additional steps to do step c.! Notice that Step c. is the dominant step here so we can only count them.The speed of how the number of steps grows as more people attend is significantly faster than the two previous instructions. In fact, the steps grow in the squared number of visitors and this type of algorithm has quadratic time complexity and is denoted as O(n^2) (Salem A., 2017).You can visually understand the number of operations between different time complexities by referring to the figure above (Fig.2).  There are more kinds of time complexity than these three, but these three examples are enough for people to understand the meaning and relationship with the size of data.

• Why is time complexity important?
  As shown in Fig.2, the number of operations of algorithms with different time complexities significantly varies. Thus, knowing how to find the correct time complexity is essential for programmers to build an efficient algorithm. This may not sound very crucial when the speed of computers keeps getting faster and faster. However, the time complexity gets more meaning as the number of data grows. Note that even the world’s fast computer takes more than a billion years to handle data of size 1000.
  We live in a world full of programs, imagine even one application with 10 million users significantly slows down. This is likely to happen if the developers of the application accidentally increase the time complexity of one of the application’s features, and it would cause a lot of losses to millions of people. Thus, as a rule of thumb, a good programmer should make an algorithm no slower than O(n^2) to ensure the algorithm runs in an affordable time(Salem A., 2017).

Work Cited

1. Epp, Susanna S. Discrete Mathematics with Applications. Pacific Grove, Brooks/Cole, 2019.

2. Mejia A. How to find the time complexity of an algorithm? Adrian Mejia Blog. Published October 3, 2020.https://adrianmejia.com/how-to-find-time-complexity-of-an-algorithm-code-big-o-notation/#:~:text=For%20any%20loop%2C%20we%20find

3. Salem A. An Easy-To-Use Guide to Big-O Time Complexity. Medium. Published March 1, 2017. Accessed June 9, 2022. https://medium.com/@ariel.salem1989/an-easy-to-use-guide-to-big-o-time-complexity-5dcf4be8a444#:~:text=Quadratic%20Time%20Complexity%20represents%20an

4. Team GL. Time Complexity Algorithm | What is Time Complexity? GreatLearning. Published December 12, 2020. https://www.mygreatlearning.com/blog/why-is-time-complexity-essential/