Week 1 - Introduction and Binary Search and Big O Flashcards
What is an Algorithm?
An algorithm is a specific set of instructions designed to perform a particular task. Algorithms are fundamentals coding elements; they define the steps a program must take to solve a problem or achieve a goal
What is a Data Structure?
A data structure is a particular way of organizing and storing data. Efficient data management relies on appropriate data structures for each task or application.
What are the areas in software development where algorithms are used?
- Data Processing
- Machine Learning
- Cryptography
- Graph Theory
What are the names of 7 Data Structures?
- Array
- Linked List
- Queue
- Stack
- Hashtable
- Tree
- Graph
What is the naive approach for searching a list for a specific element? (Brute force/ Simple Search)
The naive approach is to check each element in the list one by one until the target is found or the list ends. It is O(n) linear time in the worst case.
What is a Search Problem?
A Search Problem involves finding a specific item or value within a collection of data.
What is the Binary Search algorithm?
The binary search algorithm finds a target’s position in a sorted list by repeatedly halving the search range until the target is found or the search space is exhausted. If found, it returns the index; otherwise, it returns None. (Only works with sorted data!)
What are the differences between binary search and simple search?
Simple search is much simpler than binary search, but binary search is much more effective for larger amounts of data.
What is the order of time complexities in Big O notation, from fastest to slowest?
- O(log n) –> Logarithmic Time
- O(n) –> Linear Time
- O(nlog n) –> Log-Linear Time
- O(n^2) –> Quadratic Time
- O(n!) –> Factorial Time
What does Big-O notation show?
Big-O notation shows how an algorithm’s running time increases as the input size increases. It is used to compare algorithms. It does not indicate time in seconds, but rather “worst-case run time”.
