Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

If given an algorithm to traverse a graph (say with a breadth first traversal algorithm). And say you code it in the same manner described in this video tutorial shows (starting at 04:30 for breadth first).

Then you were asked to do an Analysis of the correctness and complexity of the code. What things will you set your mind to think about in analysing the algorithm?

I mean let us start with Correctness Analysis .. is it simply a matter of setting my algorithm to work on 100s and 1000s of different graphs and if the traversal of all of them is a success I say "Yep, I have analysed this and it is correct!"

Or is there more to it? How would you analyse the correctness of a piece of code?

Also complexity .. there are so many parameters to complexity, but I'm guessing with it being an Algorithm, it'll be useful to talk about that n metrics stuff, n to the power of 2 and so on .. that is complexity is it not? The higher the power of n, the more complex the algorithm. How can I figure out the power of n for some code?

How do you determine the complexity of an algorithm?

share|improve this question

closed as not a real question by Robert Harvey, Martijn Pieters, MichaelT, Jimmy Hoffa, Dynamic Mar 17 '13 at 22:05

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

    
What is your question? –  Robert Harvey Mar 16 '13 at 20:25
3  
for correctness, start with amazon.com/Discipline-Programming-Edsger-W-Dijkstra/dp/… –  Steven A. Lowe Mar 16 '13 at 22:18
    
These are really two very different questions. –  Thomas Owens Mar 16 '13 at 22:58
    
@StevenA.Lowe I heard a lot of praise about the Code Complete book too, so went ahead and bought it (wasn't cheap) but then as I started reading it, it seemed so abstract for me. :( Maybe I am not at that level yet, I don't know, but judging from the reviews, that Dijkstra's book will be similar. –  Ciwan Mar 16 '13 at 23:34
2  
@Ciwan: that Dijkstra book invented correctness proofs for code (weakest precondition calculus). It's not something you read, it's something you study. ;) –  Steven A. Lowe Mar 17 '13 at 0:39

1 Answer 1

up vote 1 down vote accepted

Code correctness can mean many things, but I would consider the following aspects:

  1. Function input/output correctness; Check if you get correct return value for every possible function call.
  2. Case analysis; If statements and switch-cases should have all their cases checked for correct behaviour.
  3. State analysis; Behaviour of the system checked when all possible data/state values are considered.

  4. State change analysis; What happens when system moves from one state to another.

  5. Bounds checking; Memory and array limits
  6. Performance; time behaviour of the algorithm
  7. Predictability analysis; Whether the algorithm sometimes results in random or unpredictable results
  8. Accuracy; Whether the result of algorithm has small amount of error
  9. Error propagation When problems do happen, how large is the footprint of the failed part of the system
share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.