Clever Geek Handbook

Time complexity or Big O code

I have this array which has a max heap property. The time complexity of deleteMax is O (logn). If the code below would only be repeated 7 times, what would be the time complexity of the code below (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. First: time complexity O (7 * logn) or just O (logn).

Then the second is O (1/2 * n * logn) or O (nlogn), since 1/2 is just a constant, and I guess since the number of iterations is 7, which is almost the same as half of the heap_size, I can ignore 1/2. So O (nlogn)

Which one will be correct?

+3


source to share


4 answers


In general, it makes no sense to talk about complexity when the number is fixed (aka constant). The whole purpose of the notation is to evaluate how the runtime changes when the number changes. A constant number of loops will never change the execution time or complexity. If you change the number of loops to a different constant value, it will change the execution time , but the complexity will be the same.

A typical use is to calculate the complexity of a function to give the user of the function an idea of ​​how the runtime 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 when the execution time changes when any input changes.

So, in your case, it still deleteMax

defines complexity, i.e. still O (log n). Just because there is no input that changes the number of cycles.

+5


source


If the loop only runs 7 times, then the complexity is O (1). This is because the loop is independent of the size of the data and will always run at constant time.



+1


source


Here, both the heap size and the number of loop cycles are constant. So the code will have O (1) time complexity, i.e. constant time complexity.

0


source


I think you are tipping the heap sort algorithm and I am pretty sure the complexity is O (nlogn).

0


source






More articles:


All Articles