Search code examples
algorithmtimetime-complexitycomplexity-theory

What is the time complexity of a timetabling scheduling problem if we iterate through all the possible solutions?

In the timetabling scheduling, there are n number of sections and each section further has m number of courses registered in it. Total slots available are 25, 5 per day.

Considering there are n number of sections, so n number of timetables will be created (one timetable for each section) and each section's timetable must contain all the courses assigned to that section.

I was wondering that if I were to iterate through ALL the possible combinations in this timetable, what would be the time complexity?

Please note that the timetable will be generated considering all the sections at one time, and not separately for each section. That is, one solution would contain all the courses assigned on random timeslots for each section's timetable.

Then next solution would be changing the timeslot of one course of one section while keeping the timetables of other sections same as they were in the first solution.

I can't seem to figure out the way to calculate time complexity for such a problem if we apply brute force (that is, iterate through all the possible solutions). The way I did it, it came out to be O ((m*n)^25) however, I am not sure about it. Can anyone help me figure out the correct time complexity for this?

Solution

  • If I understand it correctly, We have 25 slots for each section. Then you need to fill those sections' timetables, you need to put all m courses in the timetable. Hence, m must be less than or equal to 25.

    So, first, we should count the number of possibilities for each section. Accordingly, we need to select m of 25 to put them in the corresponding timetable first. Then count their combination which is m!. Hence, the total number of possible timetables for each section is 25!/((25-m)!m!) * m! = 25!/(25-m)!.

    Second, we can accordingly count the total number of combinations between sections. Thus, as we have n sections, we need to multiply these numbers of combinations of each section to find the total number of combinations in all sections. Hence, the total number of possible ways to create time tables are (25!/(25-m)!)^n.