Explore the basics of Big O notation and how we use it to compare the runtime complexity of operations for a given data structure. Learn the difference between constant time and linear time algorithms.
- Different operations like inserting, accessing,…and searching on different data structures…take different amounts of computational time.…To be able to compare these operations…on various data structures independently of input,…we use something called Big O Notation.…Big O Notation is used to describe…the performance or complexity of an algorithm.…Let's think about the operations…we've used so far on a race.…We've inserted items, accessed items,…searched for items, and more.…
For each of these, we can come up with its time complexity…or how long it takes to run independently of input.…As long as we know the item's index,…accessing it within the array…takes what we call O of 1 Time or constant time.…This means that the algorithm executes…in the same time or space regardless of the size of input.…When we access an item by index,…it does not matter if the array…has a million items or just two items.…It takes the same amount of computational time.…
This is also true for updating items in an array.…We simply access the item at a given index…
- Data types: Booleans, numbers, strings, and more
- Multidimensional arrays
- Jagged arrays
- Search and sort arrays
- Linked lists
- Stacks and queues
- Hash functions and hash tables
- Trees and graphs
Skill Level Intermediate
Understand data structures1m 25s
1. Introduction to Data Structures
4. Stacks and Queues
5. Hash-Based Data Structures
6. Trees and Graphs
- 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.