Algorithm Data Structure Simple Instructions Time Complexity Runtime Asymptotic Analysis Limit Lemma L’Hopital’s Rule
<aside> 💡 An algorithm is a sequence of instructions (ordered instructions) that solve a well-defined problem. A well-defined problem involves a clearly defined input and output. Understanding the expected input/output is key to solving a well-defined problem.
A data structure is a way to organize data that will be received as input or be working with in an algorithm. Data structures do not represent how this data is stored. The organization of data is different from how it is stored on a computer.
These concepts play a role in how algorithms are analyzed from a theoretical and real-life perspective.
</aside>
<aside> 💡 Execution is done sequentially. Actions must be one after the other, not in parallel. And each step is unique in the moment.
Simple instructions consist of…
Simple instructions take exactly one unit of time. This model defers from a low-level perspective where fetching an instruction from memory would be faster than getting it from secondary storage. In the case of this model, all simple instructions are just one unit of time.
</aside>
<aside> 💡 What does “one unit of time” mean? In terms of Big O Notation, “one unit of time” translates to constant time $O(1)$. Thus, simple instructions have a time complexity of $O(1)$, constant time.
****Let’s walk through an example to see how simple instructions are $O(1)$.
</aside>
int x = 4; //Intialization - 1 unit
x = x + 5; //Assignment & Addition - 2 units
cout << x << endl; //Printing - 1 unit
//Total Units of Time: 4 units
<aside> 💡 Analyzing the runtime of the code snippet, it is determined that it has a time complexity of $O(4)$.
**Initialization** + **Assignment** + **Addition** + **Printing
$O(1)$** + **$O(1)$** + **$O(1)$** + **$O(1)$**
Since $O(4)$ is in constant time, it can be graphed as $y=4$. $O(1)$ can also be graphed as $y = 1$. Both $O(4)$ and $O(1)$ are constant lines, so $O(4)$ can be simplified down to $O(1)$. Time complexities should be written down to the simplest form.
Thus, this code snippet has a time complexity of $O(1)$.
</aside>
<aside> 💡 Analyzing Algorithms consists of how long an algorithm takes from the size of its input. In other words, its the length of time comparison vs. the input size. The size of input will govern how fast an algorithm can perform.
</aside>
<aside> 💡 The runtime, the number of operations performed, of for and while loops is:
The Time Complexity Of The Statements Inside The Loop $\times$ # of Iterations
</aside>