Landing : Athabascau University

COMP372 PROBLEM 1-1

 
 

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

  • Erika Racette September 28, 2021 - 7:24pm

    Interesting solution for the last row n!. Now that's a creative work around. It's cool to see what different methods everyone's using to solve the same question. 

  • Keondre Branch January 31, 2024 - 4:24pm

    Wow this is an old one. You broke the solution down very well and made it simple to understand. Desmos is still around so I’m sure this will be helpful to anyone who didn’t know that work-around. Hope you’re doing well in life.

COMP372 Design and Analysis of Algorithms

COMP372 Design and Analysis of Algorithms

This is for course discussion.