Algorithm Complexity Simplified

  • The concepts explained here might not help you crack competitive examinations like GATE as they focus on mathematical definition rather than practical usage. But this will simplify things to make those concepts understand easily.
  • The pre-requisite to this blog is an understanding of various sorting algorithms, arrays, data structures (stack, queue, binary tree), and recursion.

Why Algorithm Complexity?

What is Algorithm Complexity?

Big Omega, Big O, and Big Theta

Drop the Constant and Non-Dominant terms

1. public void calculateSumAndProduct(int nums[]) {
2. long sum = 0;
3. long product = 1;
4. for (int num : nums) {
5. sum += num;
6. product *= num;
7. }
8.
9. System.out.println(sum);
10. System.out.println(product);
11. }
Runtime Comparison of O(N) and O(2N+1)
Runtime Comparison of O(N²) and O(N²+N)
1.  public void calculateSumAndProduct(int nums1[], int nums2[]) {
2. int sum = 0;
3. int product = 1;
4. for (int num : nums1) {
5. sum += num;
6. product *= num;
7. }
8.
9. for (int num : nums2) {
10. sum += num;
11. product *= num;
12. }
13.
14. System.out.println(sum);
15. System.out.println(product);
16. }

Best, Worst, and Expected Case Complexity

  1. Best Case: When the number we are searching for is found at the first index of the array, the runtime becomes O(1).
  2. Worst Case: When the number we are searching is at the last index of the array, the runtime becomes O(N).
  3. Expected (Average) Case: In real life, we never get too lucky or unlucky in most cases, and hence Expected Case is the most practical one. The runtime for searching a number in an array is O(N/2) = O(N).

Runtimes

Constant Runtime

1. public int sum(int a, int b) {
2. int c = a + b;
3. return c;
4. }

O(N) Runtime

1. public void print(int nums[]) {
2. for (int num : nums) {
3. System.out.println(num);
4. }
5. }

O(N²) or O(N^N)

1. public void print(int nums[][]) {
2. for (int i=0; i<nums.length; i++) {
3. for (int j=0; j<nums[i].length; j++) {
4. System.out.println(nums[i][j]);
5. }
6. }
7. }

O(log N) and O(N log N)

Binary Search INPUT on every iteration

O(2^N)

1. public int fibonacci(int N) {
2. if (N <= 1) {
3. return 1;
4. }
5. return fibonacci(N-1) + fibonacci(N-2);
6. }
Fibonacci function calls after every execution

Cheatsheet for Runtimes Comparison

Comparison of all runtimes

Appendix 1: Recursion

--

--

--

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Make Your Python Code Look Pretty

Top 10 Java Software Development Companies to know in 2022

Remote Desktop Into Kali Linux from an External Network

ASRock bios example for setting Wake-on-LAN

Real People, Real Stories: Generating Infographic ROI Report PDF From Low-Code App

10 ways SaaS can do more harm than good for your business in 2021

How to become an Android Developer

Monitoring engineering licenses mission impossible with executable files

Use java based low code platform to build enterprise applications

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Aditya Solge

Aditya Solge

More from Medium

Everything you want to know about the Stanford part-time MSCS

Well I’m here today to talk about Algorithms..

Algorithms vs Heuristics

0–1 Knapsack Problem: Integer Programming