Join Raghavendra Dixit for an in-depth discussion in this video Introduction, part of Introduction to Data Structures & Algorithms in Java.
- [Instructor] In this chapter, we'll talk about how to analyze algorithms, that is, figure out how good they are. Now, this is slightly mathematical and theoretical, and many people don't get it in the first shot. So what I suggest is that you watch it at least once now, just to understand the terminology because it will be used in later chapters. And then when you have seen some algorithms and written some code yourself, you may revisit this chapter later, all right? And in this chapter, we'll deal with the Big O notation.
When we talk about algorithms, there are two kinds of consideration that may be worth thinking about. How much space does it take to store data in memory to execute the algorithm? And how much time does it take for an algorithm to run? The first is said to be dealing with the space complexity of an algorithm, while the second one is said to deal with the time complexity of the algorithm. Now that RAM and memory, in general, is really cheap, we don't care so much about the storage of data, or we don't really bother how much space will be consumed to store the data.
So when we talk about analyzing an algorithm, we mostly worry about its time complexity. That is, we would like to know how much time does an algorithm take? So that's what we'll focus on in this chapter. But how do we measure time for an algorithm? I mean, the same algorithm running for the same input will take different times when running on different kinds of machines, right? Or even if they are running on the same machine but in different environments, where the CPU may get hotter and hence slower in one case cannot be ignored.
For example, what if the air conditioning where the machine was kept was not so good? So it would be really hard to talk about some absolute time that an algorithm may take to run. Now think about this. What if we wanted to find the best way to go from home to office or college? In terms of time, one may argue that it depends if someone who runs fast is running, or a small child is walking, or one is going by a car, or whatever.
So the time will be different for who and how are they traveling. And even for the same person with the same transportation, the times could be different for different days depending on the traffic conditions probably. So can we not talk about the time in terms of the number of the steps in walking, assuming the step size to be uniform? That is, can we not say that the best path to take is the one which has the smallest number of steps? That would be one step to abstract out or remove the complexity involving the environmental factors.
Or who or how are they traveling, right? So we choose a similar approach in studying the time complexity of an algorithm
Note: This course was created by Packt Publishing. We are pleased to host this training in our library.
- Why study data structures and algorithms?
- How to calculate the time complexity
- Using Big O notation
- Using basic sorting and search algorithms
- Searching elements in unordered arrays and ordered arrays
- Implementing a linked list in Java
- Implementing stacks using arrays
- Queues using arrays
- Binary search trees
- Representing heaps using arrays
Skill Level Intermediate
1. Introduction to Algorithms
2. Analysis of Algorithms
3. Basic Sorting and Search Algorithms
4. Linked Lists
5. Stacks and Queues
7. Binary Search Trees
8. More Sorting Algorithms
- Mark as unwatched
- Mark all as unwatched
Are you sure you want to mark all the videos in this course as unwatched?
This will not affect your course history, your reports, or your certificates of completion for this course.Cancel
Take notes with your new membership!
Type in the entry box, then click Enter to save your note.
1:30Press on any video thumbnail to jump immediately to the timecode shown.
Notes are saved with you account but can also be exported as plain text, MS Word, PDF, Google Doc, or Evernote.