Estimate the order of growth of algorithm from run time and ratio of change -

-

i'm beginner practising algorithms. below list represents algorithm ran , recorded times , ratio of change. i'm not sure how figure out order of growth list. factors have consider? appreciate explanatory answer.

 n  |seconds | ratio | log(base of 2) ratio --------------------------------------- 512   0.12    4.14      2.05 1024  0.49    4.24      2.08 2048  2.08    4.24      2.08 4096  8.83    4.24      2.08

compare times smallest input various larger inputs:

  • a 2x increase in n (512->1024) results in 4x increase in running time.
  • a 4x increase in n (512->2048) results in 16x increase in running time.
  • an 8x increase in n (512->4096) results in 64x increase in running time.

from this, can extrapolate kx increase in n result in k2x increase in running time, indicating o(n2) algorithm.


Comments

Post a Comment

Popular posts from this blog

c++ - No viable overloaded operator for references a map -

-
i trying use map can make tag names reference number. when try , use it, in code error (6 in total every time reference map): src/main.cpp:25:45: error: no viable overloaded operator[] type 'std::map<std::string, std::string>' const char* idcs = node.child_value(tagmap[3]); this code: #include "pugi/pugixml.hpp" #include <iostream> #include <string> #include <map> int main() { pugi::xml_document doca, docb; std::map<std::string, pugi::xml_node> mapa, mapb; std::map<std::string, std::string> tagmap {{"1", "data"}, {"2", "entry"}, {"3", "id"}, {"4", "content"}}; if (!doca.load_file("a.xml") || !docb.load_file("b.xml")) { std::cout << "can't find input files"; return 1; } (auto& node: doca.child(tagmap[1]).children(tagmap[2])) { co
Read more

java - Custom OutputStreamAppender not run: LOGBACK: No context given for <MYAPPENDER> -

-
i wish write custom appender on basis of outputstreamappender . wrote following class package tests; import java.io.ioexception; import java.io.outputstream; import ch.qos.logback.core.outputstreamappender; public class myappender<e> extends outputstreamappender<e> { public myappender() { system.out.println("myappender created"); setoutputstream(new outputstream() { @override public void write(int b) throws ioexception { throw new unsupportedoperationexception(); } }); } } then wrote following runner: package tests; import org.slf4j.loggerfactory; import ch.qos.logback.classic.logger; public class runner { private static final logger log = (logger) loggerfactory.getlogger(runner.class); public static void main(string[] args) { //log.addappender(new myappender<iloggingevent>()); log.info("hello world"); } } finall
Read more

java - Cannot secure connection using TLS -

-
i'm trying establish secure socket connection between java client applet (built jdk 1.7.0_75-b13) , vc++ server application. as test vehicle, used vc++ client/server sample found in msdn forums, modified use schannel , able establish socket using cipher suite tls_rsa_with_aes_128_cbc_sha. works of tls 1.0/1.1/1.2. when try opening socket java applet same server application, connection rejected server reporting following: tls 1.0 acceptsecuritycontext failed: 0x80090327 tls 1.1 acceptsecuritycontext failed: 0x80090331 tls 1.2 acceptsecuritycontext failed: 0x80090331 this java code used create socket: debugprint("setting secure connection"); sslsocketfactory sslsocketfactory = (sslsocketfactory) sslsocketfactory.getdefault(); sslsocket sslsocket = (sslsocket) sslsocketfactory.createsocket("127.0.0.1", socketnumber); debugprint("starting handshake"); sslsocket.settcpnodelay(true); sslsocket.setsolinger(false, 0); sslsocket.s
Read more