big o - Intro to Algorithms (chapter 1-1) -

-

just reading book fun, isn't homework.

however confused on first main assignment:

1-1 comparison of running times

for each function f(n) , time t in following table, determine largest size n of problem can solved in time t, assuming algorithm solve problem takes f(n) microseconds.

what mean?

the next table shows bunch of times along 1 axis (1 second, 1 minute, 1 hour, etc), , other axis shows different f(n) such lg n, sqrt(n), n, etc.

i not sure how fill in matrix because can't understand question. if f(n) = lg n, it's asking largest n can solved in, example, 1 second, problem takes f(n) = lg n microseconds solve? last part mean? don't know how set equations / ratios solve problem because literally can't put meaning of question.

my hangup on sentence "assuming algorithm solve problem takes f(n) microseconds" because don't know refers to. time what algorithm solve what problem takes f(n) microseconds? if call f(100) it'll take lg 100 microseconds? need find n f(n) = lg n microseconds = 1 second?

does mean lg n microseconds = 1 second when lg n microseconds = 10^6 microseconds, n = 2^(10^6)?

for each time t, , each function f(n), required find maximal integer n such f(n) <= t

for example, f(n) = n^2, t=1sec = 1000 ms:

n^2 <= 1000 n <= sqrt(1000) n <= ~31.63 <- not integer n <= 31

given function f(n), , time t, required find maximal value of n, , fill in table.


Comments

Post a Comment

Popular posts from this blog

Java 3D LWJGL collision -

-
i making 3d java game lwjgl library, , wondering how add collision detection, player not go through models. i using obj models. here objloader class, loads models: package renderengine; import java.io.bufferedreader; import java.io.file; import java.io.filenotfoundexception; import java.io.filereader; import java.util.arraylist; import java.util.list; import models.rawmodel; import org.lwjgl.util.vector.vector2f; import org.lwjgl.util.vector.vector3f; public class objloader { public static rawmodel loadobjmodel(string filename, loader loader){ filereader fr = null; try { fr = new filereader(new file("res/"+filename+".obj")); } catch (filenotfoundexception e) { system.err.println("couldn't load file!"); e.printstacktrace(); } bufferedreader reader = new bufferedreader(fr); string line; list<vector3f> vertices = new arraylist<vector3f...
Read more

spring - SubProtocolWebSocketHandler - No handlers -

-
i have ugly error during deploying spring app on jboss. 18:11:16,025 error [org.apache.catalina.core.containerbase.[jboss.web].[default-host].[/consumer]] (msc service thread 1-7) exception sending context initialized event listener instance of class org.springframework.web.context.contextloaderlistener: org.springframework.context.applicationcontextexception: failed start bean 'subprotocolwebsockethandler'; nested exception java.lang.illegalargumentexception: no handlers @ org.springframework.context.support.defaultlifecycleprocessor.dostart(defaultlifecycleprocessor.java:176) [spring-context-4.1.3.release.jar:4.1.3.release] @ org.springframework.context.support.defaultlifecycleprocessor.access$200(defaultlifecycleprocessor.java:51) [spring-context-4.1.3.release.jar:4.1.3.release] @ org.springframework.context.support.defaultlifecycleprocessor$lifecyclegroup.start(defaultlifecycleprocessor.java:346) [spring-context-4.1.3.release.jar:4.1.3.release] @ org.s...
Read more

methods - python can't use function in submodule -

-
my folder structure this: pythonstuff/ program.py modulea/ __init__.py foo.py bar.py here's code bar.py : def hello(): print("hello, world!") here's code program.py : #!/usr/bin/env python3 modulea import bar bar.hello() i run $ python3 program.py somehow error: file "program.py", line 3, in <module> bar.hello() attributeerror: 'module' object has no attribute 'hello' edit: __init__.py file empty. edit2: after trying realized had bar.py in root directory contained hello() method. bar.py in modulea/ directory empty. add it import os __all__ = [] module in os.listdir(os.path.dirname(__file__)): if module != '__init__.py' , module[-3:] == '.py': __all__.append(module[:-3]) the init .py files required make python treat directories containing packages; done prevent directories common name, such string, unintentionally hiding v...
Read more