You’ve read that a “Good Algorithm” is one that is less time-consuming.
It is easy, but you should solve these questions. If ten algorithms are available for the same problem and you must compare the running times of these algorithms, how can you know which algorithm will take more time and which algorithm will take less time?
.
Que 1– For larger n, which grows faster, log n or √n?
Ans – We take log n ≈ √n
Taking log on both sides
→ log (log n) ≈ log (√n)
→ log (log n) ≈ log (n1/2)
→ log (log n) ≈ ½ log (n)
So, log (log n) < constant.log n
√n grows faster than log n, you can check by hidden trial rule
n = 1 | n = 4 | n = 16 | n = 64 | n = 256 | |
Log n | 0 | 2 | 4 | 6 | 8 |
√n | 1 | 2 | 4 | 8 | 16 |
At n = 16, log n is also 4 and √n is also 4 but when n > 16 then √n will grow much faster than log n.
.
Que 2- For larger n, which grows faster n! or nn?
Ans –
n! = n * (n-1) * (n-2) * (n-3) * … * 2 * 1 (upto n terms)
nn = n * n * n * n * … * n (upto n terms)
nn grows faster than n!, when n > 1.
.
Asymptotic Analysis
We want the algorithm we have chosen to take the least amount of time. In this problem, we have 7 types of algorithms, and their time complexity is also given, you just have to identify which one will have the lowest time complexity, and we will apply the same algorithm in our program.
The time complexity of A5 is the lowest (log n), so we will apply this algorithm in our program.
One more thing, you have been given two questions above; most of the problem is in identifying the growth of (log n, √n) and (nn, n!). I have given the answer and if there is any problem then you can remember a sequence.
For larger n, the growth of time complexity is
Log n < √n < n < n log n < n2 < n3 < 2n < 3n < n! < nn
Note – The question with nn will never come because its complexity is maximum. It’s like asking you where do you live? So, you answer that I live on this earth. Everybody lives on this earth, there is no new thing.
Test Yourself
Q1- Arrange given terms in ascending order for large n.
Time complexities is – n2, nlogn, n, 2logn, 4logn, 3n, 2n, n√n
One thing should be in your mind. In algorithm, default log base is 2.
If we go through the input then we can say in full confidence
n < nlogn < n√n < n2 < 2n < 3n
but there has been a confusion between 2logn and 4logn.
-> formula is [alogax = x]
-> n = 2logn
Also,
-> 4logn = 22*logn
-> 4logn = 2logn^2
-> formula is [alogax = x]
-> 4logn = n2
The correct ascending sequence is
n = 2logn < nlogn < n√n < n2 = 4logn < 2n < 3n
Q2- Arrange given terms in ascending order for large n.
Time complexities is – √logn, (loglogn)2, logn*loglogn, logn/loglogn, √logn/loglogn
Let n is very large and a perfect square
Suppose n = 22^36
√logn = √236 = 218
(loglogn)2 = 362 = 24*2 = 28
logn*loglogn = 236*36 = 236*24 = 240
logn/loglogn = 236/36 = 236/24 = 232
√logn/loglogn = 218/24 = 214
So, the ascending order is
(loglogn)2 < √logn/loglogn < √logn < logn/loglogn < logn*loglogn
Q3- Arrange given terms in ascending order for large n.
Time complexities is –
(√n)logn
(logn)logn
(loglogn)n
(logn)√n
nloglogn
n2
Taking log
- Logn*log√n,
- logn*loglogn,
- n*logloglogn,
- √n*loglogn,
- loglogn*logn,
- 2logn
Let n = 22^100
- 2100*(1/2)*2100 = 2199
- 2100*100 = 2107
- 22^100*log100 = 22^100*27
- 100*22^50 = 22^50*27
- 100*2100 = 2107
- 2*2100 = 2101
So, the ascending order is
n2 < nloglogn = (logn)logn < (√n)logn < (logn)√n < (loglogn)n
Q4- Arrange given terms in ascending order for large n.
Time complexities is
-> 1, 2, n1/n, n1/logn, (logn)1/logn
Taking log
-> Log1, log2, logn/n, logn/logn, loglogn/logn
Let’s say n = 22^100
-> 0, 1, (2^100)/(22^100), 1, 100/2100
The ascending order of time complexities is
-> 1 < n1/n < (logn)1/logn < 2 < n1/logn
