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 <rahul23111...@gmail.com> 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 <atul.87fri...@gmail.com> 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 <dondod...@gmail.com> 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 <rahul23111...@gmail.com> 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 <rahul23111...@gmail.com
> >> >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 algogeeks+unsubscr...@googlegroups.com.
> >> 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 algogeeks+unsubscr...@googlegroups.com.
> > 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 algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
