Effective Algorithms for Dart and Flutter. Big O.
Probably the most important part of a technical interview is the knowledge check for Algorithms and Data Structures. This is the must-have part of learning curve of a professional programmer in any language, especially for a Flutter.
The glory mission of Flutter is to write code for mobile devices. Mobile devices need a special attention to performance of its algorithms and effective memory usage. We don’t have the luxury of vertical scaling by upgrading server hardware for higher CPU and Memory here. Adding the superpower of effective algorithms, you literally can create faster and more stable code for Android and IOS. That’s why interviewers will stress-test your ability to do so.
Before any further reading, let’s do one check. Did you hear about leetcode? If yes, just continue the reading. If not, please spend some 10–15 minutes just walking around problems and community pages at this website. This is the reflection of industry trends in the whole process of interviewing and selection of a new programmer for a job or a remote project.
By the way, I’m going to explain some of most important leetcode problems in the upcoming parts of this topic.
Today we’ll try to understand the core principle or even law which we can use for estimation of the efficiency of any algorithm.
This knowledge, together with some Knowledge-Map of tricks and methods to improve the efficiency, is forming this “scary” part of IT.
Algorithms Matter
The first step to attack Algorithms and Data Structures is to accept understanding why they are so important.
Let’s consider a very simple Flutter app. This app has to count the sum of increasing sequence of integers like [1, 2, 3, 4, …].
We’ll use FlutLab.io and also you can grab the initial project from FlutLab’s WidgetBay . If you didn’t used FlutLab before, this is an online Flutter IDE where you can register and build your apps for free. If you already have an account, go to the initial project on WidgetBay and click “Fork to FlutLab IDE”.
Now you can find this project in your profile:
Go inside this project and run Web Build. You should see “Result: 0” in the center of Web emulator:
The calculation part of this app was made as an independent Dart class named “Algo”:
Currently it contains just a placeholder for method “perform”, returning 0.
That’s why we can see “Result: 0” when running this app:
Now let’s implement Algo to calculate the sum of elements of a list:
Easy, right? Let’s just run web build or hot reload again:
All looks good. And actually, usual Flutter developer will happily stop here.
But can we improve this solution?
Yes!
How to see that this solution is not ideal? Lets open the other part of our project containing unit tests of the algorithm:
Here we have 2 unit tests:
- Algo should work correctly
- Algo should work effectively
Let’s run this test bundle by click on “run test” button:
We can see, that the first test “Algo should work correctly” passed, but the second one, “Algo should work effectively”- failed.
This is because it took longer then 100 milliseconds, set as max allowed time for the algorithm execution:
Big O comes to help
We can change the code of unit test and can notice, that this test is passed for some not very big arrays.
So, the time which our algorithm needs to finish is some function of the size of the its input — array of numbers.
Big O notation gives us the simple criteria to estimate the speed or time complexity of our algorithm.
In this approach we should not estimate the physical time which algorithm needs. Because this time depends on the performance of our computer and how many background work it is doing.
But we can estimate the order of that time relatively to the size of input data.
For example, time to finish (let’s use time complexity term) can be in order of 1, n, n² etc. Where n is the size of data to process.
Respectively, time complexity of an algorithm can be O(1), O(n), O(n²)
O(1) is the Holy Grail of Algorithms and Data Structures — the most optimal algorithms have this time complexity.
O(n) is acceptable, but not so good. And O(n²) is the pure evil.
How to calculate the time complexity of our Algo implementation?
By counting of operations!
If we have the input array with size of n, how many logical operations will do our code?
1 operation for sum initialization
n operations for the loop
1 operation to return the value
Excellent! We have time complexity O(n + 2). Not so fast. When we need to know the order of time complexity, we should truncate all the constants. No matter we have O(2n), O(4n+3) or O(1000n + 2000), we should just mention the fact that time complexity is the linear function of n. The right answer here is O(n).
Don’t worry if you still did not completely get the conception of Big O. We’ll revisit the calculation of time and space complexity for different algorithms.
Wait a minute! — You can say. Can we really rework this algorithm to be an order of a constant, O(1). Yes, my friend, we can.
Let’s remember that we are summing the linearly growing numbers. Starting from 1 and each next value is greater by 1.
We can draw a small figure, where numbers to sum marked with dark color:
Where X axis is the position of an array item and Y axis is its value. We added 0’s element with value 0 to show one interesting phenomena: the sum of all items is the total area of the rectangle n*(n+1) divided by 2. Indeed, dark cells is occupying exactly one half of the space of big rectangle.
So our new algorithm should look like
It’s 2 operations, irrelevant to the size of input array. So, it’s O(1).
With this change all our tests passed successfully:
Conclusion. Algorithms and Data Structures is a complex and extensive Knowledge Base. However, we can learn it practically. The critical, small subset of its methods and terms allow us to write more effective code and pass coding interviews. Today we learned that even simplest algorithm can be optimized by just counting its operations. Also, we met Big O notation. We’ll see more examples soon to solidify our Big-O-instincts and form our new mindset.
To be continued..
