I'm trying to understand how both of these algorithms, separated by a) and b), have a time complexity of O(n), could you explain how this is? a) int i = 0; while (i < n) { ... i++; } for(int j = 3; j < n * n; j += n) { ... } int k = 1; while (k < n) { ... k *= 2; } b) for(int i = 1; i < n; i += 3) { for(int j = 3; j < 10; j++) { for(int k = 5; k < n; k += n) { ... } } }
I'm trying to understand how both of these
a)
int i = 0;
while (i < n) {
...
i++;
}
for(int j = 3; j < n * n; j += n) {
...
}
int k = 1;
while (k < n) {
...
k *= 2;
}
b)
for(int i = 1; i < n; i += 3) {
for(int j = 3; j < 10; j++) {
for(int k = 5; k < n; k += n) {
...
}
}
}
Time complexity of an algorithm means the number of steps/time required to solve the entire algorithm as a function for the given input. It is used to describe the performance of an algorithm and this helps us to determine if a given algorithm is scalable or not. It means that it determines whether algorithm going to scale well as the input grows really large.
Step by step
Solved in 3 steps