big theta for quad nested loop with hash table lookup

Question

for (int i = 0; i < 5; i++) {
    for (int j = 0; j < 5; j++) {
        for (int k = 0; k < 5; k++) {
            for (int l = 0; l < 5; l++) {
                look up in a perfect constant time hash table
            }
        }
    }
}

what would the running time of this be in big theta?

my best guess, a shot in the dark: i always see that nested for loops are O(n^k) where k is the number of loops, so the loops would be O(n^4), then would i multiply by O(1) for constant time? what would this all be in big theta?

Answer 1

The big-theta running time would be Θ(n^4).

Big-O is an upper bound, where-as big-theta is a tight bound. What this means is that to say the code is O(n^5) is also correct (but Θ(n^5) is not), whatever's inside the big-O just has to be asymptotically bigger than or equal to n^4.

I'm assuming 5 can be substituted for another value (i.e. is n), if not, the loop would run in constant time (O(1) and Θ(1)), since 5^4 is constant.

Answer 2

If you consider that accessing a hash table is really theta(1), then this algorithm runs in theta(1) too, because it makes only a constant number (5^4) lookups at the hashtable.

However, if you change 5 to n, it will be theta(n^4) because you'll do exactly n^4 constant-time operations.

Answer 3

Using Sigma notation:

Indeed, instructions inside the innermost loop will execute 625 times.