CODEWITHSUNDEEP
algorithmcomplexity-theorybig-opseudocode
Patrunjel
Patrunjel

Reputation: 129

What's the big-O notation for this algorithm?

I'm currently trying to understand dynamic programming, and I found an interesting problem : "Given a chess board of nxn squares and a starting position(xs,ys), find the shortest (as in no. of moves) path a knight can take to an end position(xe,ye)". This is how my solution would sound like :

Initialize the matrix representing the chess board (except the "square" xs,ys) with infinity.
The first value in a queue is the square xs,ys.
while(the queue is not empty){
         all the squares available from the first square of the queue (respecting the rules of chess) get "refreshed"
         if (i modified the distance value for a "square")
                    add the recently modified square to the queue
}

Can someone please help me find out what's the computing-time O value for this function? I (kind of) understand big-O, but I just can't put a value for this particular function.

Upvotes: 2

Views: 1123

Answers (4)

Sam I am says Reinstate Monica
Sam I am says Reinstate Monica

Reputation: 31184

Your algorithm is worded poorly

You don't define the contents of your "queue"

you don't define "refreshed"

you're always stuck on the first square, you're not keeping track of a current square.

also, Google Djkistra's algorithm No, don't do dijkstra's algorithm. you don't have a weighted graph.

If you want to use a dynamic programming algorithm to brute force your way to an answer, I'd start at (xe,ye), and you should be able to get O(n^2) on a nxn grid

but if you consider your constraints(your piece moves like a knight, and he moves along a grid, and not an arbitrary graph) you should be able to do this problem in O(n) time

Upvotes: 1

Bogdan
Bogdan

Reputation: 944

This is a breadth first search in my opinion. It is clear that you add a square at most once in the queue and the processing of a queue entry is O(1), so the total complexity is bounded by O(N^2). However, if you can prove a theorem that tells the number of moves to get from position A to B on a NxN chess board is less than N (and intuitively this sounds reasonable for N equals or greater than 8), then your algorithm will be O(N).

Upvotes: 0

akhisp
akhisp

Reputation: 675

Sounds somewhat like Dijkstra's shortest path algorithm. In which case it is O(N^2), you're finding the "distance" for all possible paths from source to destination in order to determine the lowest one.

Upvotes: 0

Vaughn Cato
Vaughn Cato

Reputation: 64308

Because you are using a queue, the order that you process the squares is going to be in order of minimum distance. This means that you will only ever modify the distance value for a square once, and therefore the time will be O(n^2), since there are n^2 squares.

Upvotes: 1

Related Questions