DEV Community: GourineAyoubPrf

Data Structures and Complexity Part 3: linear Data Structures Stacks and Queues.

GourineAyoubPrf — Tue, 15 Dec 2020 19:48:06 +0000

Stacks :

Definition :

a stack is a linear data structure that respects the principal of LIFO “Last In First Out” it means that the last element that was entered into the stack will be the first element to get out or the principal of FIFO “Fist In First Out”which means first in first out so the first element entered to the stack will be the first element that gets out, it’s used to model real world problems and it has tow main operations pop() which is used to get the first top element in the stack and push() which is used to add an element at the top of the stack along side with other operation like peek and ifEmpty that will discuss later.

Why we use stacks ?

Stacks are used to solve many problems since it mimics the behaviour of many real world problems so it’s used as a model of those problems things like :

the undo mechanism in the text editors .
used in compilers in things like storing the recursive calls and in syntax checking.
used in DFS (Depth First Search) algorithm in graphs.
used in so many algorithms because it can model a lot of real world problems.

How to implement a stack ?

Mainly there is two ways to implement a stack either you use arrays or linked lists and in our example we will use linked lists.

this data structure is already implemented in most of the languages and the implementation sometimes is different from one language to another one , but for the sake of understanding the mechanism of it, we will implement it with it’s operation.

Stacks and Complexity :

The following operations push , pop, peek,isFull,isEmpty all has a O(1) time complexity cause they all depends on a simple instructions but if we want to do something like search an element that will take O(n) time complexity since we have to pull every element and put it back in order to loop over all the elements.

Solving a problem using stacks ( balanced brackets problem) :

In this part we will take a problem and try to solve it using the stack and as an example we are taking the famous balanced brackets problem where you need to check if the syntax and the closing of the parenthesis is correct or not in a group of parenthesis ex :

{()} ==> correct.
{()]} ==> false.
{()[] ==> false.

Input : a string containing the parenthesis → Output : true or false.

Solution :

In order to solve it using stack what we could do is to add each parenthesis to the stack one by one and each time check if the stack is not empty if the first element in the stack is the right one in example if we are adding the ‘(‘ and the the first element in the stack is ‘)’ then we simply delete the first element from the stack but if not we add the element that we wanted to add and at the end of all the string that we are looping over it’s characters (parenthesis) we check if stack is empty then we return true else we return false that’s indicates that there is a syntax error.

Queues :

Definition :

A Queue is a linear data structure that models a real world queue with tow main operations dequeue and enqueue , the queue is similar to the stack but it has tow entry's for the operations one entry for enqueuing elements (from the end) and the other will be for dequeuing elements (from the front) so that the queue will follow the principal of FIFO (First In First Out) in a way that the first added element is the first accessed.

Why we use Queues ?

Queues can be used to model many real world problems like :

waiting lines .
request in web sites to know which client should be served.
BFS (Breadth First Search) in graphs.
keep track of the added elements.
manage shared resources between some entities like CPU processes.
asynchronous data transfer.

How to implement a Queue ?

As the stack the queue can be implemented using the arrays or the linked lists data structures , in our implementation we will use linked lists.

this data structure is already implemented in most of the languages and the implementation sometimes is different from one language to another one , but for the sake of understanding the mechanism of it, we will implement it with it’s operation.

Queues and Complexity :

The basic operations of the queue like enqueue ,dequeue, peek and isEmpty will take O(1) time complexity but operations like contain (search) and remove an element from the middle will take O(n) time complexity since it’s required to dequeue all the element and enqueue then again.

Solving a Problem using Queues ( BFS algorithm) :

we will try to solve the BFS algorithm with queues (we will talk about tree data structure in the next’s articles).
Considering that we have a tree T we want to search for an element X using the BFS algorithm it means that we will go through the tree elements knowing that we go to through the breadth of each branch first.

Input : tree T , value X → Output : true / false (or you can return the value if it’s found and -1 else).

The steps will be the next :

add the root of the tree to the queue and market as a discovered node or a visited node.
loop over the queue elements and each time do :

check if the dequeued element is equal to the value that we are searching for and if true return true .
loop over the nodes that are in the same line as the node that we dequeued it means the adjacent nodes and for each node do :
add the node to the queue and mark it as visited or discovered

and at the end if the loop ended without returning a value that means that the value is not found and we must return false.

in this solution the methods markeNode(),isMarked(), getAdjacentNodes() are methods for the tree structures that are used for : mark a node as visited, check if a node is visited or not, get the adjacent node of some node in a the tree.

Conclusion :

stacks and Queues are so important in Data structures world and with no doubt they are a must know concepts for all programmers.
some real world problems require some specific data structures that can model the real world problem into something can be manipulated by the programmer with the best experience in terms of complexity , so you should always seek to know different data structures and concept in order to have many perspectives and different views for the same problems and make your own data structure if it’s the best way.
understanding the concept of the data structure is the key to know how to use in the best way.
Hope you had a good reading and learned something from that and stay tuned for the next article about another Data structure.

this article is also published by me in meduime :
https://gourineayoub-prf.medium.com/data-structures-and-complexity-part-3-linear-data-structures-stacks-and-queues-5e8e1e72a041

Data structures and Complexity part2 : linear data part1 (arrays and linked-Lists)

GourineAyoubPrf — Fri, 11 Dec 2020 20:20:13 +0000

Linear data structures is one of the most used DSs in programming it has many different Data structures like arrays linked-lists stack …etc , in this article we will talk about this tow DS arrays and Linked-list ,they are so important and basically every programmer should know about this tow even if he’s is just starting his career he will find arrays and linked lists in the first topic that he will learn due to there importance as a way of storing and manipulating data in a lot of problems.

Arrays (static arrays and dynamic arrays):

Static arrays :

a static Array is a static data structures that allow you to store any type of data as long as the length of the array is specified at the creation of it, this length can’t be changes since it’s a static DS . Each value in an array has an index that refers to it and gives the programmer a way to access it’s value knowing that the indexes start from 0 to n as an example: the first element of an array of integers will be : integerTable0, the type of data stored in the array in most languages has to be the same type for all values. (ex: all integers or all string , not a few of integers and some other data types).

when you should use static arrays ?

when you know the max length of your array.
most of the time static arrays are used as temporary memory to store objects.
used to return multiple values from a function.
used as buffers for input and output.
used to store results of the sub solutions like in dynamic programming.

Dynamic arrays :

a dynamic array is an array that has no limit to the number of value that you can put in and has the same operation that you can apply to a normal static array.

when you should use dynamic arrays ?

basically when you don’t know how much data you need to store.

How you can implement a dynamic array ?

The code source for the dynamic array is in this file :
https://github.com/GourineAyoubPrf/ArrayAndLinkedLists/tree/main/src/arraysandlinkedlistes

one of the ways to make a dynamic arrays is to use static arrays like this :

at first we have a table of length 1
each time the user want to add an element to the dynamic array we test the length of the initial array
if there is place to add : add the element normally in the next index.
if the size is not enough then:

create a new array that has a double size of the previous one.
copy all the element from the previous array to the new .
add the new element to the new array .
and finally the new array becomes our initial array and we repeat this process each time when there is no enough space to add.

in case of the deletion :

create a new array with the size of number Of elements in our initial array -1.
copy all the elements except the element that we want to delete.
the new array becomes our initial array.

this data structures are already implemented in the >programming languages but to understand them more and get >good in working with theme you need to understand how they >are implemented and how they work.

the implementation is different from one language to >another some operation are allowed in one language and not >in another but now that you know how things works if >something is not good for you you can implement your own >data structure and make the operations that you want for it.

in java we use this sign example : in the >class declaration so we can use the generic types in our >array implementation so it supports all data types. and we >implement the iterator interface in case you want to use >iterator to loop over the elements.

Array Operations :

arrays as a data structures has many operations that can be applied to. We have basic operations like :

search
add
access element
remove element. and some more complicated and specified operations like :
remove element at index / remove the first/ remove the last.
sort the elements.
invert the table elements
shift elements
… etc.

Array operations complexity :

The complexity is different from the static array to dynamic array , and also it can be different in one language to another due to the way of implementation but generally this is it :

we are talking about worst case here because there is some >search methods that can take less time if the array is >ordered (we will talk about searching and sorting methods in >another article).

How arrays are sorted in the memory ?

Arrays are stored in a contiguous space in memory as an example if you have an array of length 10 the compiler will have to find 10 successive places in the memory to store the data (places mean the pace necessary for storing one element of the specified type) , this behavior is only with arrays since it uses indexes so the memory address has to be side to side but it’s different with other DS like linked list (will discus later).

Why indexes start from 0 in arrays ?

a little story :

At the first creation of arrays in the programming world the address of the array was set to be the address of the first element of that array so they are the same address in the memory , as an example if we have an array of integers named myArray with this values [5,2,6,8,91,100,235] if we say that the address of the first value “5” that we access it like this myArray[0] is the address named 111 (just a a naming ) then the address that reference to the array it self is 111 and when the programmers implemented the arrays (low level implementation) to access an array value they did this operation as example : myArray[5] for the compiler to know it’s place he must do this operation :
the address of myArray[5] = the address of MyArray + 5 so the address will be 111 + 5 = 116 then he will go to the memory the address 116 an read it value and give it to you as the value of myArray[5] in our case it will be 100. now after you know that imagine that we start from 1 and not 0 and we want to access the value of myArray[1] the compiler have to find the address so 111 + 1 = 112 but the address 112 contains 2 not 5 which is wrong because our first element is 5 and the compiler need each time to do -1 after the sum sow he can get the write result and this will be not good for the performance because we are talking about low level implementation , for that the element’s start from 0 and not from 1.

to be more clear the address of the element that we try to access is calculated with this formula :
address of accessed element = address of the array + index * >(size of one element of the type that the arrays contain).
Example : if we say an integer take a size of 5 to store one >element then :
address of accessed element = address of the array+ index * >5 (because each integer take a size of 5 in the memory) , >Because each case has a size fit for one element of the >declared type.
If you want to learn more about this you can search about >heap memory and memory management in the operating systems .

Linked list (single linked list, double linked list and circular linked list) :

Single linked-List (also called just linked-lists):

A linked list is dynamic data structure that let you store any type of data and with no size limits since it’s dynamic , but with a new concept so that each list element or also called node has :

a value with a type specified at the declaration.
a pointer that point to the address of the next node in the list.
for the last node his next pointer points to the null value so it’s a special case that indicates that this is the end of the list.

How linked list are stored in memory ?

Not like the arrays that need to allocate a memory at the start of the creation because it has a known size that needed to be allocated , the linked list don’t need to allocate a contiguously space in the memory because each element has a pointer towards the next element of the list so it does not matter where is the place of the next element as long as it has it’s pointer it will always know where to go next until it reaches the null pointer (end of the linked list).

Where and Why we need linked-Lists ?

implementing another data structures like stack queues and graphs.
used to model real world problems like a trains.
used as a solution for the hash collision problem in the hash data structures(a problem know in the hash based data structures) .
one important this is that in arrays if you delete an element that element space still exists but you can do something like put a special character or number (based on the type) in it that it indicates that this element was deleted but the space will be always allocated and can’t be changed unless you delete the whole array but in the linked list as an advantage of the chaining concept with pointer you can delete an element and it’s space in the memory because the memory get allocated and freed each time you add or delete an element.

How can i implement a linked list ?

The code source for the Linked List implementation is in this file :
https://github.com/GourineAyoubPrf/ArrayAndLinkedLists/tree/main/src/arraysandlinkedlistes

this data structures are already implemented in most of the >languages . In our example we will use java language as a >tool to implement the linked list you can use any language >you want the concept want change just the syntax. Each >linked list has a pointer of the head and a size property >(you can add other properties if you want)and as we know >each node has a next pointer and a value.

Linked-lists operations complexity :

Add at head :

Since we already have the head pointer so this will take O(1) time complexity because we need just to change the pointer of the head to the new node and link the new node with the previous head.

Add at tail :

In this case we assumed that we don’t have a pointer of the tail so in order to get that we need to loop over all the list nodes then point the last node next pointer to the new node and point the next pointer of the new node to null so it indicates that it’s the last node.

you can make this also o(1) if you memorize the tail address >in your implementation.

Add at a specified Index :

First we have to find the node that correspond to that index and for that we need to loop until we reach that node after that it’s just a matter of changing pointers the new node next pointer will point to the current node next and the current node next pointer will point to the new node and . And generally it will take O(n+1/2) time complexity so we can say it’s O(n).

Remove Head :

Since we have a head pointer this will be a O(1) time complexity and all what we need to do is :

make the head pointer point to the current head next pointer then clear the head node.

in our case in java there is something called the garbage >collector so as long as an object has no reference to it it >will be cleared but in some other language you have to free >the space manually.

Remove tail :

Just as adding at the tail we need first to find the node that is before tile with a loop then we do the next :

point the current node next to null. And this will take O(n) time complexity.

Remove at a specified index :

For this we have to loop over the list nodes so we can get the node that we are deleting after that we can do :

point the next pointer of node that is before the index to the next of the deleted node. and it will be an O(n) time complexity.

Search for a value:

It’s simple just a loop over using a pointer and if we reach the null pointer it means that the element was not found in the list , complexity will be O(n).

Double linked-lists :

A doubly linked list has the same behaviour as the normal linked list (single linked list) but each node has one more info and that is a pointer to the node that is before him so basically each node has 3 information :

a pointer to node that is before him : before
a value with a specific type : value.
a pointer to the next node after him : next.

the head before pointer and the tail next pointer will be >null as indicator of the start and the end of the list.

How can i implement a double-linked-list ?

Each double linked list has a pointer at the head and the tail of the list and a size proprieties . Each node has tow pointer before and next and a value.

the implementation can be changed as you want as long as you >keep the same concept because at the end this data structure >is meant to help you not make it more complicated so you can >always tweak the implementation to solve the problem that >you want or add new operations for the list as you need.

Double-Linked-Lists operation complexity :

The code source for the Double linked lists implementation is in this file :
https://github.com/GourineAyoubPrf/ArrayAndLinkedLists/tree/main/src/arraysandlinkedlistes

Add at head :

The same it’s will stay o(1) and doing the flowing steps :

point the new node “before” pointer to null.
Point the “next” pointer of the new node to the head .
Point the “before” pointer of the head to new node.
Make the list head pointer points to the new node.

Add At tail :

This will be O(1) following the next steps , since we have a tail pointer we just need to do :

point the head “next” pointer to the new node.
point the new node “before” to the tail of the list.
point the new node “next” pointer to null.
make the tail of the list is the new node.

Add at a specified index :

Just as single linked list we need to loop over the list to fond the element with that node , the time complexity will be O(n) and the steps will be the following :

find the node that correspond to that index (let’s name it node X).
make the new node “before” pointer point to node X.
make the new node “next” pointer points to node X “next” pointer.
the previous “next” node of X (lets name it Y).
make the “before” pointer of Y points to the new node.
make node X “next” pointer points to the new node.

Remove at head :

Same as linked list will take O(1) :

lets name the “next” node of the head node X.
point node X “before’ pointer to null.
the new head will be node X.
garbage collector will do the rest since the head has no reference to it it’s space will be freed.

Remove at tail :

This will take O(1) time complexity with this steps :

let’s name the node that is before the tails (the before of the tail) node X.
point the node x “next” pointer to null.
make the list tail point to the node x.

remove at a specified index :

This will be O(n) :

first we need to find the node correspond to the index and we use 2 pointers.
let’s name the node at the index node X.
lets name the node before the node X node Y
lets name the node that is after node X node Z.
point node node Y “next” to node Z.
point node Z “before” to the node Y.

the search operation is the same it will take O(n) time >complexity and the we use the same principal in searching >just a pointer that will loop until we reach the end.

Single linked list vs double linked list :

single linked list will have no “before” pointer mean;s you can’t go backward but in the same time it will store less data.
with double linked list you will have the ability to go through list in the tow direction but with the cost that it has more space cause it has 1 more information to store.

Circular linked List :

Circular linked list is another linked list type basically it;s the same as the double linked list but instead of the head before pointer point to null adn the tail next pointer point to null we have :

the before pointer of the head will point to the list tail.
the next pointer of the tail will point to the list head.

in this way the list will be circular in a way that you will loop over the list nodes as long as you want with no stop unless you store the head address or the tail address and check for them in order to stop.

Conclusion :

arrays and linked list are tow of the most commune Data structures so any programmer or a software engineer need to know and understand how they work.
when you want to choose what to use between arrays and linked list try to see what;s the most commune operation that will be done in your algorithm then base on that take the data structure that does that operation with less time complexity , as you know there is no good or bad data structure it;s all about what you are using in for.
when you are using a programming language try to see the implementation and the method given to the data structure that you are using cause it may be different from one language to another.
knowing the difference between how the linked list get stored in memory and how the dynamic arrays are stored in memory is so important not because they are both dynamic means that they have the same time complexity .
hope you had a good reading and you benefited from the article , next article will be about tow other linear data structures : stacks and queues.

this article is also available in the medium website you can >visit this link :

https://gourineayoub-prf.medium.com/data-structures-and-complexity-part2-linear-data-part1-arrays-and-linked-lists-713a53360e64

Data structure and complexity a programmer best tow weapons (part 1 : introduction)

GourineAyoubPrf — Fri, 04 Dec 2020 17:50:22 +0000

Being a software engineer does not mean only that you should know how to build programmes it also means that you should aim for the best performance that you can get from what you are building to give the user the best experience , in order to do that as a software engineer you should know the different types of DS’s (data structures) and how to use theme plus how to get the best out of your solution using the complexity analysing.
Data structures :

Definition :

My definition : data structure is a way of organizing data with some specific rules in order to solve various programming problems , each data structure has it’s own pros and cons or more like a place where it will be best to use it based on what it can offer to the programmer , each data structure has it’s own operations and relations between the data that it contains also the nature of the data that is stored in it.
wiki : a data structure is a data organization, management, and storage format that enables efficient access and modification.More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data
A data structure is a specialized format for organizing, processing, retrieving and storing data.

why we use data structures ?

we use data structures as a tool for storing any kind of data that we are manipulating in our algorithm.
Data structures are used in computing to make it easy to locate and retrieve information.
without DS (Data structures) it will be impossible to treat a huge amount of data with no errors.

why you should learn data structures ?

if you know a lot of DS it’s guaranteed that you will use the right DS in the right place.
knowing more DS will make give you the ability to know how to lower the complexity (we will talk about it later ) and maximize the performance of your algorithms.
a lot of famous algorithms is implemented in some specific DS so to understand it you have to understand the DS that is implemented with.
you will have more than one solution for your problems so that you can choose the best one .
save memory by using the best fit DS for your algorithms.

Data structures types :

there is a lot of DS each one has it’s own rules,way of manipulating,relations between it’s data , the format of it’s stored data , complexity but on general we can group the DSs in four forms :

linear : list , arrays , stack ,queues, linked lists.
trees : binary tree , AVL tree , black/red tree. , heaps …etc.
hashes : hash-maps , hash-tables.
graphs : decision, directed … etc

note : we will discuss each DS in depth in the next parts >of this articles series.

Types of operations that can we make for a data structure :

As a DS is way of organizing and manipulating data it means that we can apply some operation on the data that we are storing and basically the operation can be one of this following or ones that are similar to it :

adding / pushing .
removing / deleting .
updating .
sorting .
merging .
retrieving.

note :

there is also other operation that can be done only to >some types of DS , so some operation are based on the type >of the DS that you are using each DS support a bunch of >operation.

the way of the operation is handled and what is the >result of the operation may be different from one DS to >another based on how it store the data and manipulate it.

what is an algorithm complexity ?

in programming , solving the problem is not everything because some time the solution is not applicable in real world applications or it exceeds the resources that a company have so for the same problem most of the time there is more then one solution , the next step after finding a solution that works for the different test cases is to optimize it , and here we have tow axes that we focus on :

1. Time complexity :

it means the time that your algorithm will take to give a correct result after giving it an input (if there is inputs ) and to make it more formal when programmers study the complexity of there solution they use one of the complexity notation as an example big notation (will discuss later). we measure the time and complexity in terms of the growth and and the number of operations relative to the input size n.Usually, the time required by an algorithm falls under three types :

Best Case − Minimum time required for program execution.
Average Case − Average time required for program execution.
Worst Case − Maximum time required for program execution.

2. space complexity :

Here we are talking about the amount of space your algorithm will allocate in order to solve the problem most of the time the space will be freed after the end of the algorithm(we are not talking about data base space here) but the problem is when your algorithm consumes a lot of memory by time your program will crush and it will cause the system to crush to.

note : in this article we focus more on time complexity.

Asymptotic bounds :

in order to measure the complexity we need some formal ways to do that for each solution and for that we have a 3 Asymptotic bounds :

big-omega : which gives you the lower bound.
big-o : which gives you the upper bound.
big-theta : which gives you both the upper and lower bound.

note :

The annotation it self is not related to the best,worst or >average solution , each annotation can be applied to >calculate worst, best or average of the solution that you >have done.

big-Theta is good because it gives you both bounds but >it’s hard sometimes to prove it .

if big-theta of a function f is X then it means that big-o >of this function f is also X but not the inverse unless that >big-omega is also equals to X.

the Asymptotic bounds are based on a mathematical >functions and they allow you to give a complexity to a >solution that you implemented and by result you can compare >tow solutions and take the best based on that.

How to calculate Big-o notation ?

big-o is a notation used to the upper bound time of an algorithm it means the worst case scenario which we always get interested in because if the worst case is good for the you don’t have to worry about other cases.

note : some operation like push /pull / add has different >complexities based on the type of the data structure that >you are using as an example : to search for a value in a >hash-table DS that will be O(1) in best case and o(n) in >some other cases (hash collision cases) but in a linked-List >that will always be O(n).

asymptotic notations for the big-o :

1. constant O(1):

basically each simple instruction in your algorithm has a constant time complexity noted as O(1) this simple instruction are operations like this :

a variable declaring.
a value assigning to a variable.
a condition test.
accessing an array value by index.

2. logarithmic O(log n):

An algorithm is said to run in logarithmic time if its time execution is proportional to the logarithm of the input size. usually this type of complexity will exist if the number of iteration that you are doing in your program will get divided to half each iteration as an example : first iteration : 20 → second iteration : 10 → third iteration : 5 … etc.

This kind of behaviour is used in a one of the best algorithm paradigm know as divide and concur an as an example we have the binary search of a value in a sorted array :

in this algorithm the number of iteration is divided to half each time and we choose the half that we continue with based on the value of the searched element so the complexity here will be O(log n).

note : the data can be divided by more then 2 (in this case >the logarithm base get changed as example : divide by tow it >means log base 2 and if you divide by 4 it means log base 4 >…etc).

3. linear O(n) :

Linear time complexity will appear when we have to do a simple instruction but n times usually that n refers to the length of a data structures that we will loop overt it’s elements or a counter in a loop as an example a for loop with a condition of index< n where n is the length of our list :

so the complexity of this loop here is the complexity of the condition + the complexity of the loop core * n (number of repetitions) and since we take the worst case in big-o so we say that this complexity = O(1) + O(n) = O(n)

note : if the condition contains a function call or the loop >core itself contains a function call then we need to take >that in consideration and calculate the called function >complexity first then we multiply it by n(number of repetitions).

3. n log n complexity O(n log n) :

As we already talked about the O(log n) and the O(n) complexity the O(n log n) is just a form of repeating the log n complexity n times as an example we can take the quick sort algorithm as an example where the data will be divided and treat each half and sort it and repeat this until the table is sorted so we have the divide and concur mechanism that will take O(log n) time complexity and O(n) time complexity for the iteration through the table , in this implementation we are using a recursive mechanism :

the formula of complexity (because it;s recursive) is T(n) = 2T(n/2) + O(n) and after you solve it you will have a complexity of O(n log n).

4. quadratic O(n²):

this complexity appears often when we have a nested loop (a loop inside another loop) as in example the algorithm that prints all the elements of a matrix will be like this :

in this case we have the first loop that will repeat I times and inside it each time the second loop will repeat j times and since we consider the number of repeated times as n so we have n repeated n times so its O(n2)

note : In general, doing something with every item in one >dimension is linear, doing something with every item in two >dimensions is quadratic, and dividing the working area in >half is logarithmic.

5. cubic O(n³) :

Here we have the same principal as the quadratic complexity but we add one nested loop inside so it will be 3 loops as an example we have this situation : a list that has a matrix as a value and we need to loop every matrix and print it’s values.

since we already know that the complexity of the matrix print algorithm is O(n2) the we just have to multiply it by n and that give us O(n3).

6. exponential O(2^n) :

so we already know that in the logarithmic complexity the data is divided by tow but here we have the complexity will grow after each iteration , this is more likely to happen with recursive calls as an example the Fibonacci sequence algorithm :

7. factorial O(n!) :

this is one of the worst complexity that you should always avoid (if you can) and it appears in the problem of finding Find all permutations of a given set/string.

complexity for recursive functions :

for recursive function it’s a bit different to calculate the complexity since we have to do a mathematical analyses of the algorithm and proof it complexity throw the iterations , and there is also many rules depends on the shape of the recursive functions , example :

if we take the Fibonacci algorithm as an example and try to analyse it’s complexity we will find the next :

the if condition and the return 1 will always be of complexity O(n)
this line {return Fibonacci(n-1) + Fibonacci(n-2) } has tow functions calls it means in order to calculate it’s complexity we need to calculate the called functions complexity and since it the same function called in a recursively we need to format it in a formula :

Where T(n) = our complexity and n = the number that we want to calculate for the Fibonacci sequence. And c is a constant with O(1) complexity represent the first part before the functions call.

1et iteration : T(n) = T(n -1) + T(n-2) + c =

2end iteration : T(n) = 2 (T(n-1) + T(n-2) + c) + c

3ed iteration : T(n) = 2(2 (T(n-1) + T(n-2) + c) + c) + c

……

k iteration : 2^k * T(n — 2k) + (2^k — 1)*c // approximation.

After this you need to find the k value and replace it in the last formula to find the complexity. For this solution the complexity will be O(2^n)

note 1 : each recursive function will be solved in a >different way depends on the number of calls that it has and >the way of the data is handled (is the data getting smaller >by dividing or by subtracting a value from it …etc).

note 2 : sometimes to make the complexity better consider >using another approach for solving the same problem as an >example if you are using recursive way try using dynamic >programming (this paradigm will be discussed in the next >articles).

conclusion :

Data structures is a major thing that you need to know at least the famous and most used of theme in order to become a better programmer , each time you learn a new DS you will have a new view or a new perspective on how to solve a problem based on the philosophy of that new DS and the more you get used to different DS the more different solution you can get for the same problem and the most important you will know which DS is the best to use with that problem ion order to give you the best performance.
Time and Space complexity is a one of the important axis that based on we judge the efficiency and the quality of the solution and it goes along side with understanding the DS that you work with because if you don’t then you can’t neither calculate the complexity of your solution nor optimizing it .
the more you solve programming problems and try to optimize them the more you will get experience and get to know a variant of new DSs , make sure you do your best and keep learning every day “ we are never old to learn new things “.
hope you got some new information from this article and it benefited you , this article is just the first from a series of article that will discus different Data structures and it’s complexity.

this article is also posted on meduime : https://gourineayoub-prf.medium.com/data-structure-and-complexity-a-programmer-best-tow-weapons-part-1-introduction-a941cda2f557