Introduction

---

In this section, I am going to talk about linked lists and the notation of Big O.

Linked Lists

---

Article's summary about Linked Lists:

The text discusses the importance of organizing information and data structures in software development. Vaidehi Joshi explains that there are many tools available for organizing data, but it is important to choose the right tool for the job. One of the first things encountered when coding is data structures, which are ways to organize data. The author explains that linked lists are a type of data structure that can be difficult to understand, and it is important to have a fundamental understanding of them.

The text goes on to discuss linear and non-linear data structures. Linear structures have a sequence and order, while non-linear structures do not. Examples of non-linear structures include hashes, trees, and graphs. Arrays and linked lists are examples of linear structures, and the text explains that the biggest difference between them is the way they use memory in machines. Arrays require memory to be allocated in one contiguous block, while linked lists can use scattered memory. The author explains that arrays are static data structures, meaning they need all their resources allocated when the structure is created and can't change in size. Linked lists are dynamic data structures, meaning they can shrink and grow in memory.

NOTE: Indeed, it exists a function in C programming language that allows dynamic allocation of memory, known as malloc(). Indeed, if there is 7 blocks allocated and I want another one, this function checks if there are available memory at the end of the array to add that one. Otherwise, it searches another location in memory that can allocate the 8-size block. In the worst scenario, it returns a NULL pointer.

Vaidehi Joshi also emphasizes the importance of understanding the difference between static and dynamic data structures, and how they impact memory allocation. They explain that dynamic structures can be more efficient because they do not require a set amount of memory and can change in size, while static structures may require copying data and recreating the structure with more memory to add elements.

Indeed, the text highlights the importance of choosing the right data structure for the job and understanding the differences between linear and non-linear structures, as well as static and dynamic structures. It also emphasizes the importance of understanding memory allocation and how it impacts the efficiency of data structures in software development.

Big O notation

---

Big O notation is a method used to measure the efficiency of an algorithm or function, taking into account its running time and memory space. It describes the worst case scenario in terms of efficiency that an algorithm can have when performing its task. To analyze these factors, four key areas are considered:

• Input Size
• Units of Measurement
• Orders of Growth
• Best Case, worst case and average case

Input Size refers to the size of the parameter values that are read by the algorithm, and the letter n is used to refer to this value.

Units of Measurement are used to quantify running time and memory space, with different measurements used to analyze each factor. The efficiency of running time is measured using milliseconds, number of operations executed, and the number of basic operations executed.

Memory Space is measured based on the amount of space needed to hold the algorithm's code, input and output data, and working space during the calculation. It's important to note that space and time Complexity are measured differently and should be analyzed separately, and contemporary computing affords most machines with multiple Gigabytes of working memory, making algorithm space complexity less of a concern than in the past.

"As the value of n grows, the Order of Growth represents the increase in Running Time or Memory Space."