Let's take the worst case, where the matrix is filled with ones. Say that it takes S nanoseconds to scan one location, and D nanoseconds to visit a location with DFS. We have to scan all locations in the matrix. That is row*col scans, which takes S*row*col ns. At the first location we will start a DFS which will visit all of the matrix locations. In the process it will mark them all as visited. That will take D*row*col ns. >From then on, all of the locations are marked as visited, so we don't do any more DFS.
Total time: S*row*col + D*row*col = (S+D)*(row*col) But S and D are constants, so the complexity is O(row*col). Don On Apr 26, 8:19 am, rahul sharma <[email protected]> wrote: > got the islands...but first we scan each element then also dfs for them if > all are 1..then how it can be o(row*col)...plz explain me complexity ofr > this > > > > > > > > On Fri, Apr 26, 2013 at 2:07 PM, atul anand <[email protected]> wrote: > > {*1*,* 1*, 0, 0, 0}, > > {0, *1*, 0, 0, *1* > > }, > > {*1*, 0, 0, *1*, *1*}, > > {0, 0, 0, 0, 0}, > > {*1*, 0, *1*, 0, *1*} > > > above different set of color represent different island.Simple DFS is used > > to find all the island > > > On Fri, Apr 26, 2013 at 3:11 AM, Don <[email protected]> wrote: > > >> The complexity is still O(ROWS*COLS) because each location in the > >> matrix will be visited once by the loop and once by DFS. Once a > >> location has been visited by DFS, it is marked as visited and can't be > >> visited again. > >> Don > > >> On Apr 25, 5:11 pm, rahul sharma <[email protected]> wrote: > >> > What will be complexity if all elements in matrix are 1.. > > >> > when first dfs will call then all matrix will be scanned setting each > >> > element to visited... > >> > then again loop contiues to scan all the elements..plz explain > > >> > On Thu, Apr 11, 2013 at 2:04 AM, rahul sharma <[email protected] > >> >wrote: > > >> > > {*1*,* 1*, 0, 0, 0}, > >> > > {0, *1*, 0, 0, *1*}, > >> > > {*1*, 0, 0, *1*, *1*}, > >> > > {0, 0, 0, 0, 0}, > >> > > {*1*, 0, *1*, 0, *1*} > > >> > > Can anybody eplain how there are 5 islands in above matrix..thnx in > >> advance > > >> > > source:-http://www.geeksforgeeks.org/find-number-of-islands/ > > >> -- > >> You received this message because you are subscribed to the Google Groups > >> "Algorithm Geeks" group. > >> To unsubscribe from this group and stop receiving emails from it, send an > >> email to [email protected]. > >> For more options, visithttps://groups.google.com/groups/opt_out. > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To unsubscribe from this group and stop receiving emails from it, send an > > email to [email protected]. > > For more options, visithttps://groups.google.com/groups/opt_out. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. For more options, visit https://groups.google.com/groups/opt_out.
