For your first example:
sum = 0 ;
for ( i = 0 ; i < n ; i++ ) --> n
for ( j = 1 ; j < n^3 ; j = 3*j ) --> O(log n)
sum++ ;
The second loop will be logn since we keep multiplying j by a factor of 3 each time, So the order will be O(n logn)
and not n^4
The Big O calculations for each loop is right, however, if you have a loop within a loop, you multiply the calculations.
sum = 0 ;
for ( i = n ; i > 0; i = i/3 ) --> log n
for ( j = 0 ; j < n^3 ; j++ )--> n^3
sum++ ;
The first loop here will also be of log n since you're constantly dividing by 3, So multiplying the order of the 2 loops we get:
O(logn * n^3) = O(n^3 logn)
We cannot reduce that further since we have no constants to remove.
Just to point out a simple misconception we can have for this case, normally if we have the below scenario, we can reduce it like
O(n^3 + n^2) = O(n3)
However, your scenario is not an addition of orders, it's multiplication, so again we cannot remove the O(logn)
here.
How to analyze code:
This is how I do it, lets take an example
for(i=0; i < n; i++)
for(j=0; j < n*2; j++)
for(k=0; k<n; k++)
for(l=0; l<n; l+=3)
for(m=0; m<n; m*=2)
First, find the big 0 for each loop:
for(i=0; i < n; i++) --> O(n)
for(j=0; j < n*2; j++) --> 2n = O(n)
for(k=0; k<n; k++) --> O(n)
for(l=0; l<n; l+=3) --> n/3 = O(n)
for(m=0; m<n; m*=2) --> O(log n)
Multiply the outer loops by their inner loops:
for(i=0; i < n; i++) --> O(n) * O(n) = O(n^2)
for(j=0; j < n*2; j++) --> 2n = O(n)
for(k=0; k<n; k++) --> O(n) * O(n) * (log n) = O(n^2 (log n))
for(l=0; l<n; l+=3) --> n/3 = O(n)
for(m=0; m<n; m*=2) --> O(log n)
Now we add the orders of the outer loops, so we get:
O(n^2) + O(n^2 log n) = O(n^2 + n^2 (logn))
And then we reduce the order. In this case, n^2 log n has a greater growth rate than n^2, so we can just remove n^2 since the n^2 logn will suffice to explain the growth rate. So finally, we have:
O(n^2 (log n))