why we need to learn logarithms??it is about thinking right??
and can anyone suggest me the best websites and youtube channels …to learn about these as well as how to find time complexity??
1 Like
why we need to learn algorithms??sry
Exponentiation is a common pattern in algorithms. For example, let’s say we have a balanced binary tree. Each node in the binary tree will have 2 children. If there are 5 levels, then we will have :
- 2^0 = 1 node at Level 0 (root)
- 2^1 = 2 nodes at Level 1
- 2^2 = 4 nodes at Level 2
*… - 2^n nodes at Level n.
Now, if we have a balanced binary tree with x nodes in the nth level, total number of levels is log_2(x) = n (i.e) log_base(x) is inverse of base^n = x.
An important thing to note here is that as number of nodes in each level grows exponentially (i.e) {base^1, base^2,…,base^n}, number of levels grows linearly (i.e) {1,2,3,…,n}. This is a very useful insight for complexity.
If we can design an algorithms whose run-time increase linearly as the input size grows exponentially, we say the algorithm has O(log(input_size)) run-time complexity.
1 Like
Yes someone has already spent days solving on problem problem efficiently, so we just use his hardwork. That’s algorithm.
best example is Sieve of Eratosthenes - GeeksforGeeks
you can’t think of such logics during short duration of competition, so algorithms gives us a head start.
1 Like
He wants to learn 'bout logarithm tho, not algorithms.
4 Likes