Big O notation is a way to describe how the efficiency of an algorithm or program changes as the input size grows. Imagine you're solving a problem, like finding a specific item in a list.
Big O notation helps you understand how the time/space it takes to solve this problem increases when the list gets larger.
It uses a special notation, typically written as "O(something)," where "something" tells you how the problem's complexity grows with the input size.
The most common complexities are constant, linear, quadratic and logarithmic.
O(1) means the time/space it takes to solve the problem doesn't depend on the input size - it doesn't matter how big the input size is, the time is the same. It's super fast and doesn't get slower as the list gets longer.
If a school doubles in size from 200 to 400 pupils, the school still only needs to ring the bell once for each period in the day.
Given an index, retrieving an element from an array takes constant time because it directly maps to a memory address.
What does O(1) time complexity mean?
O(n) means the time/space it takes increases linearly with the input size. If the list doubles in size, it will take roughly twice as long to find the item.
If a school doubles in size from 200 to 400 students then the time it takes to serve all the pupils food will double.
Finding an element in an unsorted list by checking each element until the target is found or the end of the list is reached.
What does O(n) time complexity mean?
O(n^2) means it takes much longer as the input size grows. If the list doubles, it might take four times as long or 4 times as much space.
Imagine that each student in a class wanted to greet every other student in the class each morning, if the number of students in the class doubled, then the number of required greetings would practically quadruple!
An elementary sorting algorithm that compares and swaps adjacent elements.
What does O(n^2) time complexity mean?
O(log N) is different. It's like a super-efficient algorithm. When the input size grows, it doesn't make the program work a lot harder. Instead, it makes it work a little harder, and the time it takes grows slowly. It's like magic when you're dealing with big datasets – it doesn't slow down much as the data gets bigger.
If a student knows some gossip, then all they need to do is pass on the gossip to 2 other students and soon the whole school will know. This is why gossip spreads so quickly!
Efficiently finds an element in a sorted array by repeatedly dividing the search interval in half.
What does O(log n) time complexity mean?
When are talking about the efficiency of an algorithm, it is important to consider two aspects of complexity:
Time complexity refers to how an algorithm's execution time changes with input size, usually measured in terms of basic operations.
Space complexity is about how an algorithm's memory or storage usage changes with input size, often measured in memory units like bytes.
When we talk about time and space complexity we also usually consider the best case, average case and worst case scenarios for each.
The best-case scenario refers to the situation in which an algorithm performs optimally and requires the least amount of resources or time.
If a teacher was looking for a student in a school with 20 classrooms, the best case would be 1 classroom would need checking.
The average-case scenario represents the expected performance of an algorithm when considering all possible inputs, typically using statistical analysis.
If a teacher was looking for a student in a school with 20 classrooms, the average case would be 10.5 classrooms would need checking.
The worst-case scenario describes the situation in which an algorithm performs the least efficiently, requiring the most resources or time to complete.
If a teacher was looking for a student in a school with 20 classrooms, the worst case would be 20 classroom would need checking.