# Introduction | Data Structure and Algorithms | Quick Notes | Back to Old days

Variable: A variable is nothing but a box with a label(its name) and a predefined type promise that you cannot be broken later. Have a look at mathematical equation below.

X + 2Y = 45

Here, the names X and Y are placeholders for some data that can justify the equation if put in their places. Similarly, in computer science programming we need something to hold data and variables are nothing but that.

Data Types: In the above example, X and Y can hold any type of value such as an Integer value(5, 10) or real value(2.0, 5.8). But to solve this equation, we have to relate them to a particular kind of value they can take and Data Type is that name used for this purpose in computer science.  Or “A data type is a set of data with predefined values used to declare variables/objects. Example: integer, float, double, character, string etc.”

In computer memory, everything is either 0 or 1. A data type is a thing that tells the compiler about what kind of values a particular set of bytes are of and depending on that the compiler takes further decisions on them.

A data type can be a predefined one or can be customized according to the need. Based on this definition criteria they fall into two categories.

1. System-defined data types(Primitive data types): As their name specifies, they are defined by the system. The primitive data type provided by many programming languages are int, float, double, char, bool etc. The number of bits allocated for each primitive data type depends on the programming language using, the compiler, and the operating system. For the same primitive type, different programming languages may use different sizes and thus their domain(total available values) will also get change. For example, int may take 2 or 4 bytes. If it is of 2 bytes then it’s domain will be -215 to 215-1 and if 4 bytes then the domain will be -232 to 232-1.
1. User-defined data types: If primitive data types are not enough, we can define our own data type fulfilling all our requirements. Classes are the best example of user-defined data types that most of the programming languages provide. Swift provides class, struct, enum and protocol, four kinds of user-defined data types.

Data Structure: Data Structure is an arrangement of data in such a way that they can be efficiently stored and retrieved. Or we can say that it is a special kind of format for organizing data. The general data structure includes Stack, Queue, Linked List, Tree, Graphs and so on.

Depending upon the organization of data elements Data Structures are classified into two types

1. Linear Data Structure: Linked List, Stack, and Queue are linear data structures as elements are arranged in a linear manner in them.
2. Non-Linear Data Structure: Tree and Graph are non-linear data structure as elements are stored in a non-linear manner in them.

We talk about Data Structures as an Abstract Model and their Concrete Implementation.

An Abstract Data Type is a logical and mathematical model defining some set of rules that have to be followed and some list of operations that have to be implemented by the concrete implementation of that model. We can think of ADT as a black box which hides the inner structure and design of a data type.

For example, an Abstract model of a Car can be… an object having four wheels, a steering, brake, accelerator, motor, some number of seats etc. etc. with on/off, run and some other operations.

A concrete implementation of an abstract model is called Concrete Data Type. For example, Duster is a concrete implementation of abstract model Car.

A list, Stack, Queue, Tree, Graphs etc. are abstract data types having some logical set of rules and operations that have to be defined by their concrete implementation regardlessly of which programming language is getting used. In Java, inside java.util package there is a “List” interface which is nothing but an abstract model of List Data Structure whereas, ArrayList and LinkedList are two concrete implementations of List ADT.

Algorithm: An algorithm is a step by step unambiguous instructions to solve a given problem. There are two main criteria for judging the merits of an algorithm.

1. Correctness: Is it solving the problem in a finite number of steps. Correction can be measured by comparing the expected and resulted output.
2. Efficiency: How much resources does it take to solve the complete problem?

Algorithm Analysis: Algorithm analysis is nothing but finding the complexity(time and space usage) of an algorithm in terms of input size, being machine independent and considering just basic computer steps. It is the only way to find out the efficiency of an algorithm so that it can be compared with others to choose the best. Complexity is considered in terms of processing time(Rate of growth), memory usage, developer efforts etc.

The rate of growth is a function which defines at what rate the running time increases as the input size increases. Let’s take an example, Suppose in a party, one guest consumes 2 bottles of water. The number of water bottles needed will be, twice the number of guests will come. Here the rate of growth of water bottle consumption is 2n, where n is the number of guests. Rate of growth function f(n) can be defined as  f(n) = 2n.

Why  Algorithm Analysis: There may so many ways to solve a particular problem. But we need the most efficient solution out of all and to get which solution is most efficient, the analysis is needed.

Types of analysis: From algorithm analysis, we basically want to know that with which input the one algorithm takes the least time and with which it takes the longest time. Based on algorithm’s measurement is divided into following 3 types.

• Worst case: Defines the input for which the algorithm takes a long time.
• Best case: Defines the input for which the algorithm takes a least time.
• Average case: Defines the input for which the algorithm takes less than longer time but more than the last time.

Let’s say there are two packets of goodies.
One packet has between 10 and 20 goodies in it (we’ll call this Packet A).
One packet has between 30 and 40 goodies in it (we’ll call this Packet B).
You can pick only one of them but you don’t know which packet is Packet A or which packet is Packet B.

Here, for you, the worst case will be, if you choose Packet A and the best case will be if you choose Packet B.

Asymptotic Notation: Asymptotic notation is kind of syntax or units that are used to express the best, worst and average cases of an algorithm.

1. Big-O Notation(Upper Bound Function): This notation represents the upper bound of an algorithm which means in any case running time will not be more than this.

In General, Big-O is used to represent the worst-case efficiency of an algorithm where lower bound is not considered. It is represented as f(n) = O(g(n)) where, g(n) is the function which represents the upper bound of f(n).

General Rule of Big-O notation:

• Ignore Constants: Example, the upper bound of 4n is n.
• Ignore lower order terms: Example, g(n)  of function f(n) = n2 + 2n will be n2 (or any value bigger than this), as n2 will be contributing more than 2n for reaching the worst case. In simple words, we have a complex function f(n) and a simple function g(n) and we want to find a constant c such as, when multiplied with g(n), the resultant value will always be greater than f(n) from some point n0 for all n>n0.

Question: Find Big-O of  f(n) = n2 + 5.

Note: n2 is the upper bound(contributing the most in rate of growth) of this equation. Let’s take g(n) = n2, but to prove f(n) = O(n2) we need to have some positive integer c and n0 which can satisfy  f(n) <= c*g(n). we can substitute any value of c that satisfy the condition. So, let’s put c = 2(or more than 2 will also be fine).

n2+5 <= c*n2

n2+5 <= 2n2

5 <= n²

Hence found, g(n) = n2 and Big-O of f(n) with c = 2 and n0 = 3.

Note: there can be any number of combination of c and n0. And if n2 is upper bounding f(n) then any value greater than n2 such as n3, n4  will also upper bound f(n) thus, they can also be big O of f(n) but we should always consider the tighter upper bound.

1. Omega-𝛀 Notation(Lower Bound Function): This notation represents the lower bound of an algorithm which means, in any case, the running time can never be less than this. Generally, it is represented as f(n) = 𝛀(g(n)) where, g(n) is lower bound of f(n).

Here, we have a complex function f(n) and a simple function g(n) and we want to find a constant c such as, when multiplied with g(n), will lower bound the function f(n) from some point n0 for all n>n0. we can say f(n) ∈ 𝛀(g(n)) if there exists c>0 and n0 >0 such that f(n) = n0.

# Question: Find Big-𝛀 of  f(n) = n + 5.

Let’s assume g(n) = n and prove f(n) = 𝛀(g(n)) by satisfying, f(n) >= c*g(n) for some c > 0, n0>0 and n>=n0 .

n + 5 >= c*n

Here, we can substitute any value of c that satisfy the condition. But looks like 1 is the only value which can satisfy this.

n + 5 >= n

Hence found, g(n) = n and Big- 𝛀 of f(n) with c = 1 and n0 = 1 for all n > 1.

Notice: there can be any combination of c and n0. And if n is lower bounding f(n) then any value less than n such as logn, log(logn)  will also lower bound f(n) thus, they can also be big 𝛀 of f(n).

1. Big-𝚹 Notation(Average Function): This notation represents the average time that can be taken by an algorithm. Generally, it is represented as f(n) = 𝚹(g(n)) where, O(g(n)) >= f(n) >= 𝛀(g(n)).

# Big-𝚹 notation defined as 𝚹(g(n)) = { f(n): there exist positive numbers c1, c2 and n0 such that  c1*g(n) >= f(n) >= c2*g(n) for all n>= n0}. Or in simple words, we have a complex function f(n) and a simple function g(n) and we want to find a constant c1 and c2 such as, when multiplied with g(n), will middle bound the function f(n) for all value for n >= n0.

Question: Find Big-𝚹 of  f(n) = n2 + 5.

Let’s assume g(n) = n2 and prove f(n) = 𝚹(g(n)) by satisfying, c1*g(n) >= f(n) >= c2*g(n) for some c1,c2 and n0 > 0 for all n>= n0

c1n2 >= n2 + 5 >= c2n2

Here, we can substitute any value of c1 and c2 which satisfies the equation. C1 = 5, c2= 1 and n0= 1 satisfying the equation.

Hence found, g(n) = n2 and Big-𝚹  of f(n) with C1 = 5, c2= 1 and n0 = 1 for all n>1.
In General, worst case is considered to tell the efficiency of an algorithm and Big-O is one used to represent that. Big-𝚹 is considered only when the Big-O and Big-𝛀 of an algorithm are same.

That’s all about the introduction of Data Structure and Algorithm but stay connected for next chapter “Linked List”. Happy Learning!! 🙂