Data Structures are structures programmed to store ordered data, so that various operations can be performed on it easily. It represents the knowledge of data to be organized in memory. It should be designed and implemented in such a way that it reduces the complexity and increases the efficiency. We select these data structures based on which type of operation is required.
I believe that by this time, now you all are good programmers as you already did a lot of programming in your previous semesters. Now you are on the track of becoming an efficient programmer. But to call yourself as a good programmer or efficient programmer, you need to learn some more things like
- you need to learn what is data structures
- you need to learn what is algorithms
Learning data structures will help you to become an efficient programmer so that you will be able to write efficient programs which will require minimum resources and will be giving the output in a very short time. Good programming is a programming style where you are getting your output by using minimal resources. We will see that how all this is possible in this course
Lets look into data structures in more details and develop good understanding of it. [Click the following links to watch the Video]
- Introduction to DATA STRUCTURES
- Abstract Data Types (ADT) [Read Text] [Download Text]
- Basics of Asymptotic Notation [Read Text] [Download text]
- Analyzing Iterative Code Program [Read Text] [Downoad Text]
You are invited to raise queries by writing your question in the box given below
Expertvision 
Good day profesor, i could not understand difference between omega and o notation, though having problem in both equations
Hello Ulug’bek,
Let me how I understand these two asymptotic notations.
Big O notation shows the worst case which means the maximum effort is required to perform the algorithm.
That is why least upper value is shown while representing big O notation
Omega notation, on the other hand, shows the best case where the minimum effort required to perform the algorithm.
So lower tight bound is provided to represent Omega notation.
Hello Ulugbek, the notation omega emphasizes that it is an ordinal number, whereas the notation 0 emphasizes its role as a cardinal number.
O(g(n) = f(n), such that 0 <= f(n) <= cg(n) for some constant c. It means that there exists some function g(n) that defines an upper bound for function f(n). For example, we have g(n) = n^2 + 1, and we need to find it's upper bound O(g(n)). Such function exists, and it's, say, 3n^2 because it's always more than n^2 + 1, so with hiding all constants it gives O(n^2). So the function n^2 + 1 has quadratic time complexity. Likewise, Ω defines a lower bound, the best case.
Omega shows you the best case, while o-notation is about the worst case.
Big O notation represents the best of the worst cases. For example, n^2 slope growth slower than any polynomial or factorial functions, which means they worse than n^2 according to asymptotic notation. So, for T(n) = c1n^2 + c2n + c3, big O will be O(n^2) which means the best of the worst for all quadratic functions, and better than polynomial or factorial functions.
Omega notation represents just the best case, which means that the function can never do better than the specified value but it may do worse.
Big O notation here f(n)Ω(g(n)), while in Big theta notations in the picture c2g(n) is upper than f(n) and c1(g(n)) is lower than f(n). So, should we express this in this way-> c1(g(n))<f(n)<c2(g(n)). But in the lecture video, it is different.
I think there is matter of the value of c,not coefficient. I mean the value of c2 can be less than c1.If you look at the example solved by professor (time 26:22 of the first video of the week2) his value of c1=4, c2=1. But at the end he wrote in order as c1=1 and c2=4. So the main point is the value of the right handside coefficient of the equation c1(g(n))<f(n)<c2(g(n)) must be greater than the value of the left handside coefficient. All in all it is my point of view and it can be wrong)
Good morning professor, I am a bit confused in omega notation. You explained it as it is best case, that’s ok. But then you gave an example where you said 7>6,5,4,3… .And 6 here is lower tight bound. But in example with functions: f(n) = 3n + 2, and g(n) = n, f(n)= omega g(n) => 3n+2 = cn; why did you take c=1, should not here c = 2, according omega notation
To satisfy the relationship 3n+2 must be greater than cn, so we should take the minimum value of c because we are interested in best case. I think it is the reason why we should take 1 instead of 2.
Actually, I think best case here is 2. Because if we take c = 2 it still satisfies our equation.
Hey everyone, I have a question regarding the topic O-notation. Professor substituted 3 instead of c in the formula f(n)=3n+2, g(n)=n cn<=3n+2. How can i know what value should i substitute instead of this c in other questions. Is there any rule for this. May be i missed this part. Thank you beforehand))
In lecture insted of c he puts 4. Look f(n) is 3n+2 it is a given function. Now 3n+2 must be smaller or equal to cn. That is 3n+2n or 2n or 3n. But if we put 4 instead of c then the inequality 3n+2= 2(n is calculated from inequality 3n+2<=4n). So whenever u have to find c u choose the smallest number when that is substitued in inequality the inequality holds after some certain n.
Good day everyone, I want to ask:
Can we combine massive with linked list to make our program work more faster by using most efficient part of them ?
As far as i know, sometimes combining different data structures into one helps to achieve better performance but one should note that using two of them most likely will result in worse space complexity. So it could result in better time complexity but worse space complexity.
When you say massive, I assume you mean an array.
At first about Linked list, a Linked list is linear data structures that hold any type of object and reference to the next object(or the next node): node consists of an object and pointer who points to the next node, the last node has a reference to null. So, the advantages of the linked list that data can be easily inserted and removed, also it is dynamic, so there is no limitation of inserting additional data due to the referencing feature. However, it allows only sequential access to its elements and uses more storage space in a computer’s memory than an array does.
Secondly, Array is also linear data structures that consist of objects of the same type and can be revealed by a specific index. Consequently, an array allows random access to the data which is very convenient. But, an array cannot efficiently removed elements as a linked list as well as it has to be resized in a large amount of data.
It follows that linked lists should be used for large lists of data where the total number of items in the list is changing. Arrays, on the other hand, are better suited to small lists, where the maximum number of items that could be on the list is known. So, we can say they are needed for different purposes and different solutions.
The main difference between massive (array) and the linked list is that in the array the elements are stored in consecutive memory locations and are referenced by an index and in the linked list every node in the list points to the next node in the list. The direct combining of them will lead to vanishing the feature of the linked list or array, however, we such combining might exist in particular abstract data type.
Good afternoon everyone,
I just want to ask about the significance and limitations of the Big O notation with an appropriate example for better understanding.
Algorithm comparison could be undertaken in different ways. For example, we could take two algorithms and run them with different inputs and compare results. What are the problems with this method. First, the algorithms could result in different efficiencies for different input. Second, the first algorithm could run better in one computer whereas second could run better in different computer(that is real algorithms are machine dependent). Third, this process could take considerable amount of time for complex algorithms with big inputs. Big O(as well as omega, theta) is machine independent, lets user classify algorithms(which makes easier to choose between them in need), it is universal(that is it could be applied to any kind of problem), and it removes the need for actual real-life tests(therefore helps us to save up some time). For example, you have to sort list of numbers in ascending order as fast as possible. You can use either selection sort or merge sort and you have list with size 10(n=1000). Now you have to decide which one of these algorithms to use. Here big O helps you to decide which one to choose.
The significance of the Big 0 notation is that it helps to calculate the approximate time of execution of the program.
So, we can easily compare two or more algorithms with each other to find an appropriate solution to our problem.
The limitation is it does not consider any constants. So, we cannot say that in some cases it will run faster. Namely, for small input, constants play dramatic roles. So, assume that we have a program that runs 0(n) having a small number of constants and 0(n^2) having twelve times larger constants than 0(n). When we have a small number of inputs 0(n) will run faster than 0(n^2) because of constants, but with an increasing number of constants to a large value, the reverse statement will be true.
This better seen in the graph. The function of n rises faster than n^2 when it is smaller than 1, then n^2 increasing quicker.
Big O notation is used to describe the complexity of algorithms. For this, the concept of time is used.
Let’s start with the simplest: O (1)
We take an array of 4 numbers:
const nums = [1,2,3,4];
Let’s say you want to get the first element. We use the index for this:
const nums = [1,2,3,4];
const firstNumber = nums [0];
How complex is this algorithm? You can say: “not complicated at all – just take the first element of the array.” This is true, but it is more correct to describe complexity in terms of the number of operations performed to achieve the result, depending on the input.
Is it advantageous if we will first perform sorting of the array before using a linear search, will the running time decrease compare to the non-sorted? Moreover, at the same time, we will perform a comparison of values, if the searching data is less than the previous then we will terminate the algorithm.
The answer is NO. If we add sorting and then searching instead of just searching, we will conversely increase run time of the program at minimum from O(n) to O(logn*n) because linear search just check element by element.
For example if we have array Wich is {3,1,5,2,4} and we want to find 5. We will find it in 3 iterations. But , if we sorted , it will require 5 iterations , so we increase our run time.
Actually adding feature of comparison of values will increase the efficiency of algorithm in certain cases. Imagine we have n input size and the value we are looking for does not exist in the list. If it is unsorted the linear search goes and looks for each entry that is it checks all n values. Where as if we have conditional to stop search one the value of entry is bigger than the value we are looking for then the search might stop in the first element or in the mid depending on the element we are looking for. But you must note that the sorting might be quite time and space consuming. Linear search over n entries with checking feature will become adaptive in the case if element does not exist in the list. Howeve one must note that the worst case of big O will not change.
How we can find running time of recursion algorithm?
There are 3 methods to find the running time of any recursion algorithm:
1. Back substitution method
2. Recurrence tree method
3. Master theorem method
Use these keywords to find more detailed information with particular examples.
Good morning, Shokhzod. First you need to write a recurrence relation for your recursion. Consider recursive binary search algorithm. We divide an array by two in each recursive call, and check whether it is our key or not. So our recursion relation will look like this: T(n) = T(n/2) + 1, where 1 is a check which is constant time operation. Using, say, back substitution method we express T(n/2) = T(n/4) + 1. Substituting it back we get T(n) = T(n/4) + 1 + 1. In a similar manner, we will divide by 2 (assuming that n is the exact power of 2) and get 1 eventually.
T(n) = T(n/2^i) + 1 + … + 1. So it’s clear that argument in T(n/2^i) shall be equal to 1.
n/2^i = 1
i = logn/log2
So the solution for recurrence is logn/log2 + 1. Since it is exact solution for our recurrence we then can state that it is tight average theta complexity. So T(n) = Θ(logn).
Actually, by professor’s logic I like build logic. Take variables and give them values from 0 till u undestand the nature of algorithm in terms of some function such as O(log n)
Are there any other techniques, rather than asymptotic notation, for analysis?
Besides traditional theoretical analysis where number of dominant operations are counted there is application-driven form of analysis used in empirical analysis. The second form is used in fields like operations research, scientific computing, and artificial intelligence.
There is an application-driven form. That is used in artificial intelligence and number of other fields.