Find the time complexity of below methods in Big-Oh
NOTE: Key is given at the end.
Try to find answers on your own before using the key.
void method0 (int n) {
int counter = 0;
for (int i=0; i<n; i++)
counter++;
}
void method1(int n) {
int counter = 0;
for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
counter++;
}
void method2(int n) {
int counter = 0;
for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
for (int k=0; k<n; k++)
counter++;
}
void method3(int n) {
int counter = 0;
for (int i=1; i<n; i=i*2)
counter++;
}
void method4(int n) {
int counter = 0;
for (int i=0; i<n; i++)
for (int j=1; j<n; j=j*2)
counter++;
}
void method5(int n) {
int counter = 0;
for (int i=2; i<n && i!=0; i*=i)
counter++;
}
int method6(int n) {
if (n==0)
return 1;
return method6(n-1) + method6(n-1);
}
Key
method0 - O(n)
method1 - O(n^2)
method2 - O(n^3)
method3 - O(log n)
method4 - O(n log n)
method5 - O(log log n)
method6 - O(2^n)