When your question is answered use !solved to mark the question as resolved.
Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For tips on how to ask a good question use !howto ask.
#Theoretical analysis on Timecomplexity
dapper portalBOT
remote summit
can you show all the code
grim widget
You need to calculate the time complexity for each part and add them together
DFS is O(n+m) on a graph if you use a neighbor-list
O(n²) if you used a neighbor matrix
spare gyro
question: How do i analyze the code with reference to prove I get the right time complexity but not include all code (and choose the parts in code to include, if one function is O(1) do i have to show the whole code and go through it to prove it???)
You only have to talk about the lines of code that affect the time complexity.
So in this code, you'd just say "for every element in the array, we loop over all elements in the array again, so this is O(n^2)". You can still mention why the O(n) loop here is irrelevant to make it extra clear you know your stuff, though:
void foo(int *arr, size_t arr_len) {
for (size_t i = 0; i < arr_len; i++) {
for (size_t j = 0; j < arr_len; j++) {
if (i != j) {
printf("%zu\n", i * j);
}
}
}
for (size_t i = 0; i < arr_len; i++) {
printf("this loop doesn't affect the time complexity, since it's O(n), so smaller than the other one\n");
}
}