Time complexity or Big O of the code

Question

I have this array which has a max heap property. The time complexity of deleteMax is O(logn). If the code below will iterate for only 7 times, what would be the time complexity of the below code (big O)?

int heap_size = 15;
int i, value, heap_array[]; // array is in the form of max heap
....
for(i = 0; i < 7; i++){ // iterates seven times
    value = deleteMax(heap_array);
    printf("%d ", value);
}

I have two solutions in my mind. First: The time complexity is O(7 * logn) or simply O(logn).

Then the second one is O(1/2 * n * logn) or O(nlogn) since 1/2 is just a constant and I'm assuming that since the number of iteration is 7 which is almost the same as the half the heap_size, I can disregard 1/2. Thus O(nlogn)

Which one would be correct?

If heap size is always 15, you have a constant time complexity here. O(1). It's not a function of the input, because there's no input. — xiaofeng.li
@LukeLee I think you need to consider the deleteMax function inside the for loop - O(logn) and also the number of iterations in the for loop? What I'm confused is that the for loop will only iterate up to 7 elements and not the whole heap_size. — labyrinthdeux
Well you picked a bad example. If the for loop runs n/2 times, that's more interesting. — xiaofeng.li

4386427 4386427 · Accepted Answer · 2017-04-12T05:45:06

In general it is pointless to talk about complexity when a number is fixed (aka constant). The whole purpose of the notation is to evaluate how execution time changes when a number changes. A constant number of loops will never change execution time nor complexity. If you change the number of loops to another constant value, it will change execution time but complexity is the same.

The typical use is to calculate the complexity of a function in order to give the user of the function an idea about how execution time changes when the user changes some input value. Example:

void foo()                 // Pointless to talk about complexity as there is no input

void foo(int x)            // Complexity tells you how execution time change 
                           // when you change x

void foo(char* someString) // Complexity tells you how execution time change 
                           // when you change the length of someString

Note: Complexity never tells you the actual execution time! Only how execution time changes when some input is changed.

So in your case, it is still deleteMax that determines complexity, i.e. it is still O(log n). Simply because there is no input changing the number of loops.

Time complexity or Big O of the code

4 Answers