Big O

Big O - Describes an upper bound on the time. This is similar to less than or equal to relationship. 

for example : Alex age is X years old ( Assume that no one lives longer than 100 years old ), then you could say X <= 100. It would also be correct to say that X <= 1000 or X <= 100000. Printing the values in an array is O(N) as well as O(N^3) or any runtime bigger than O(N).

Big Omega - Describes a lower bound on time. Printing the values in an array is omega(N) as well as omega(log N) and omega(1). Because it won't be faster than those runtime.

Big Theta - Theta means both O and Omega. Describes the tight bound on runtime.

Note : In industry, people seem to merged theta and Big O together. Industry meaning of Big O is closer to what mean by Theta, in that sense it would seen to be incorrect to describe printing of array elements in O(n^2). Industry would just say it is O(n).

Add vs Multiply :

Add the Runtimes : O( A + B)

for(int a : arrA){
  print(a);
}

for(int b : arrB){
  print(b);
}

If your algorithm is in the form "do this, then, when you are all done, do that" then you add the runtimes.

Multiply the Runtimes : O(A * B)

for(int a : arrA){
  for(int b : arrB){
    print(a+","+b);
   }
 }

If your algorithm is in the form " do this for each time do that " then you multiply the runtimes.

Some Problems asked in Interview :

Suppose we had an algorithm that took in an array of strings, sorted each string, and then sorted the full array.What would the runtime be? 

Incorrect Approach :

Many candidates reason the following:

Sorting each string - O( N log N )

We have to do this for each string - O ( N * N log N )

We have to sort the array - O ( N log N )

Total runtime complexity - O ( N^2 log N + N log N ), 

which is just O ( N^2 log N)

Reason of above approach to be incorrect : The problem is that we used N in two different ways.

In one case, N is the length of the string and in other case, N is the length of the array in above case.

Correct Approach :

s - length of the longest string

a - length of the array

Now we can work through this in parts:

Sorting of each string - O ( s log s )

We have to do this for every string - O ( a * s log s )

We have to sort all the strings(array). There are a number of strings, so you will be inclined to say that this takes O ( a log a ) time. But, we have to take the string comparison into account which will take O( s ) time. There are O( a log a) comparisons, therefore it will take O( a*s log a ) time.

Finally, we get O( a*s ( log a + log s ) ) and there is no way to reduce it further.

---------------------------------------------------------------------------------------------------------------

The following code prints all Fibonacci numbers from 0 to n. What is its time complexity? 

void allFib(int n) { 
for (int i= 0; i < n; i++) { 
System.out.println(i + ": "+ fib(i)); 
 } 
}
 
int fib(int n) { 
if (n <= 0) return 0; 
else if (n == 1) return 1; 
return fib(n - 1) + fib(n - 2); 
}

Incorrect Approach :

Many candidates reason the following:

fib( n ) takes O( 2^n ) exponential time complexity

and it's called n times, so overall time complexity is O( n * 2^n )

Reason of above approach to be incorrect : Yes, fib( n ) takes O ( 2^n ) time, but it matters what the value of n is.

Correct Approach :

Let's walk through each call:

fib( 1 ) -> 2 ^ 1 steps

fib( 2 ) -> 2 ^ 2 steps

fib( 3 ) -> 2 ^ 3 steps

fib( n ) -> 2 ^ n steps

2^1 + 2^2 + 2^3 + .............................. + 2^n = 2^n+1

So, overall time complexity is still O( 2^n )

Rate of Increase: A final way to approach the runtime is to think about how the runtime changes as n gets bigger. After all, this is exactly what big O time means.