I am trying to test what I know about BigO not very confident not totally illiterate either but please guide.
This is not a home work , I am not a student any where but interested in understanding this and various other related concepts.
//What is bigO of this Application ?
public class SimpleBigOTest {
// What is BigO of this method -> I am certain it is O(n) but just checking
private void useItirativeApprachToPrintNto0(int n) {
for (int i = 0; i < n; i++) {
System.out.println("useItirativeApprachToPrintNto0: " + i);
}
}
// What is BigO of this method -> I am reasonabily certain it is O(n)
private void useRecurrsiveApprachToPrintNto0(int n) {
if (n != 0) {
System.out.println("useRecurrsiveApprachToPrintNto0: " + n);
useRecurrsiveApprachToPrintNto0(n - 1);
}
}
// What is BigO of this method -> I think now it is O(n^2)
private void mutltipleLinearItirationsDependentOnValueOfN(int n) {
int localCounter = n + n;
for (int i = 0; i < localCounter; i++) {
System.out.println("mutltipleLinearItirationsDependentOnValueOfN: "
+ i);
}
for (int i = 0; i < n; i++) {
System.out.println("mutltipleLinearItirationsDependentOnValueOfN: "
+ i);
}
}
// What is BigO of this method -> I think this is again O(n)
private void mutltipleLinearItirationsNotDependentOnValueOfN(int n, int j) {
int localCounter = j;
for (int i = 0; i < localCounter; i++) {
System.out
.println("mutltipleLinearItirationsNotDependentOnValueOfN: "
+ i);
}
for (int i = 0; i < n; i++) {
System.out
.println("mutltipleLinearItirationsNotDependentOnValueOfN: "
+ i);
}
}
// What is bigO of this main -> I would say O(n^2) because
// mutltipleLinearItirationsDependentOnValueOfN has biggest BigO of O(n^2)
// if I am correct
public static void main(String[] args) {
SimpleBigOTest test = new SimpleBigOTest();
int n = 1000;
int j = 1234;
test.useItirativeApprachToPrintNto0(n);
test.useRecurrsiveApprachToPrintNto0(n);
test.mutltipleLinearItirationsDependentOnValueOfN(n);
test.mutltipleLinearItirationsNotDependentOnValueOfN(n, j);
}
}
As a side question why do all the books on Algorithms speak so highly of Recursion where as in my practical experience I have always used iteration. Using Recursion we can run out memory quickly and nightmare to debug.