Home > Algorithms, Computer Science, Problem Solving/Puzzles > Measuring Complexity of an Executable!

Measuring Complexity of an Executable!

For the time being, I have an interesting question to share rather ask 🙂

When ever we do the Asymptotic Analysis, we are given the source code or algorithm of a problem and we measure the run time complexity in terms of Big O, Big Omega etc…by doing the line to line analysis of the code.

Now the question is, lets say we are given an executable containing the code of a given problem (lets assume a sorting or searching algorithm), now how will we find the complexity of the executable i.e the asymptotic complexity? means is it taking linear, quadratic or exponential time etc…

Do try to think on this, it’s small but interesting question..

  1. January 17, 2008 at 4:38 am

    perhaps do a black box testing of sort where you benchmark the running time of the exe file against certain input

  2. January 31, 2008 at 6:23 pm

    agree with Tabman .. there are tools which can give us running time … any other way?

  3. umer
    June 8, 2008 at 5:40 pm

    decompile the exe to machine instruction code and then find the complexity at lower level.

  4. Rakesh Soni
    December 18, 2010 at 1:34 pm

    As this executable may be for any kind of program.
    So complexity may be calculated module wise.

    For ex. suppose exe is for some GUI then how much time it takes to launch GUI.
    second example may be like you want to open and load some large file , so how much time its taking to load that file.

    We can execute it many times and draw a graph over time and can get observe nature of graph.

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: