 ## COMP372 PROBLEM 1-1

• Public
By Craig Belair in the group COMP372 Design and Analysis of Algorithms January 12, 2020 - 11:21pm

In order to solve Problem 1-1, we first convert all times into microseconds:
1 second = 10^6 microseconds
1 minute = 60*10^6 microseconds
1 hour = 3600* 10^6 microseconds
1 month ~= 30*24*3600*10^6 microseconds
1 year ~= 12*30*24*3600*10^6 microseconds
1 century ~= 100*12*30*24*3600*10^6 microseconds

Some of our functions are elementary math operations that can be algebraically solved. Let k be the amount of microseconds determined above:

lg(n) = k → 2^(k) = n. So a problem of size floor [2^(k)] can be solved in time k.
Similarly n^0.5=k → k^2=n, so a problem of floor[k^2] size can be solved in time k.

Expressions like n! And nlg(n) cannot be solved in a simple algebraic method, however using an online graph problem like desmos and graphing y_{1}=k alongside y_{2}=zetafunction(x) and then locating the intercept and using the floor function provides us with solutions for n!=k