Landing : Athabascau University

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



Comments

These comments are moderated. Your comment will not be visible unless accepted by the content owner.

Only simple HTML formatting is allowed and any hyperlinks will be stripped away. If you need to include a URL then please simply type it so that users can copy and paste it if needed.

(Required)

(Required)


COMP372 Design and Analysis of Algorithms

COMP372 Design and Analysis of Algorithms

This is for course discussion.