" Sub-linear algorithm - O(n+k) - Radix Sort.

Space-Time Tradeoff and Efficiency

There is usually a trade-off between optimal memory use and runtime performance.
In general for an algorithm, space efficiency and time efficiency reach at two opposite ends and each point in between them has a certain time and space efficiency. So, the more time efficiency you have, the less space efficiency you have and vice versa.
For example, Mergesort algorithm is exceedingly fast but requires a lot of space to do the operations. On the other side, Bubble Sort is exceedingly slow but requires the minimum space.
At the end of this topic, we can conclude that finding an algorithm that works in less running time and also having less requirement of memory space, can make a huge difference in how well an algorithm performs.

Example of Big-oh noatation:

// C++ program to findtime complexity for single for loop

#include <bits/stdc++.h>

using namespace std;

// main Code

int main()

{

//declare variable

int a = 0, b = 0;

//declare size

int N = 5, M = 5;

// This loop runs for N time

for (int i = 0; i < N; i++) {

a = a + 5;

}

// This loop runs for M time

for (int i = 0; i < M; i++) {

b = b + 10;

}

//print value of a and b

cout << a << ' ' << b;

return 0;

}

Output

25 50

Explanation :
First Loop runs N Time whereas Second Loop runs M Time. The calculation takes O(1)times.
So by adding them the time complexity will be O ( N + M + 1) = O( N + M).

Time Complexity : O( N + M)

FilesExpand file tree

algorithms_analysis.ipynb

Latest commit

History

algorithms_analysis.ipynb

File metadata and controls