Time complexity for nested for different loop structures

Question

I have a piece of code which executes three nested for loops in the following way (written as language agnostic as possible):

for i = 0 to n - 1
    for j = 0 to n - 1
        for k = 0 to n - 1
            [do computation in linear time]

My intuition says that this should result in N^3 complexity. I'd like to compare its complexity to the following nested loops:

for i = 0 to n - 1
    for j = i + 1 to n - 1
        for k = j + 1 to n - 1
            [do computation in linear time]

Logically, it should be faster, because as i increases, the inner loops should compute faster; however, having seen countless other threads on the site explaining that the latter of those is also N^3 is confusing.

Is my assumption of N^3 for both correct, and if so, how do I quantify the differences, assuming there are any?

Answer 1

With big O notation, only the leading polynomial value is listed (i.e., in this case, N^3). The latter example you provide could be described as a(N^3)-b(N^2)-c(N)-d, where {a,b,c,d} are integers, and therefore the latter might be significantly quicker depending on how large or small i or n are. However, because you have 3 nested loops, big-O notation will still be listed as N^3.

Answer 2

The time complexity for both the above code will be order of n^3 i,e Big O (n^3). By the definition of Big O notation T(n) ≤ k f(n) for some constant k. So 2nd one code will not much more contribute for some constant k.