Generally speaking without optimization, which implementation of main is fastest
ID: 3867230 • Letter: G
Question
Generally speaking without optimization, which implementation of main is fastest and which is slowest, and what are some caveats for how fast they’ll be?
#define N (1 << 30)
#define BLOCKSIZE (1 << 10)
#if defined(MAIN_A)
int main() {
char* ptr1 = (char*)malloc(BLOCKSIZE);
char* ptr2 = (char*)malloc(4);
free(ptr1);
for (int i = 0; i < N; i++) {
ptr1 = (char*)malloc(BLOCKSIZE);
free(ptr1);
}
free(ptr2);
}
#elif defined(MAIN_B)
int main() {
for (int i = 0; i < N; i++) {
free(malloc(BLOCKSIZE));
}
}
#elif defined(MAIN_C)
int main() {
for (int i = 0; i < N; i++) {
}
}
#endif
Explanation / Answer
In an algorithm analysis all the 3 main functions take O(n) worst-case time complexity.
But, MAIN_C is fastest among all, since it doing nothing, and for loop takes O(n) time analysis.
MAIN_B for loop takes O(n) time and free(malloc(BLOCKSIZE)); runs O(1) time = O(n) * O(1) = O(n)
MAIN_A is slowest among all. It takes O(1) + O(1) + O(1) + (O(n) * (O(1) + O(1))) + O(1) = O(n)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.