CODEWITHSUNDEEP
javaalgorithmbig-o
devguy
devguy

Reputation: 41

What is the Big-O Time complexity of this recursive call with a for-loop

Question, when analyzing the time complexity of the following code (never mind the space complexity). Would this be O(n)? the recursive call count as constant? I'm not sure because of the recursive call within the for loop.

public void printViews(View view) {
        if (view instanceof ViewGroup && ((ViewGroup)view).getChildCount() > 0) {

            ViewGroup viewGroup = ((ViewGroup)view);
            int childCount = viewGroup.getChildCount();

            for (int i = 0; i < childCount; i++) {
                Log.d("Test", viewGroup.getChildAt(i).getClass().getSimpleName());

                if (viewGroup.getChildAt(i) instanceof ViewGroup)
                    printViews(viewGroup.getChildAt(i));  //recursion
            }
        } else {
            Log.d("Test", view.getClass().getSimpleName());
        }
    }

Upvotes: 3

Views: 142

Answers (2)

HaroldSer
HaroldSer

Reputation: 2065

It is O(n). Since you are traversing through the tree hierarchy once. The recursive method even though it is inside the for loop is serving the purpose of traversing the view and its descendants.

Upvotes: 3

Shuki Avraham
Shuki Avraham

Reputation: 1043

It is O(n).

What you are doing is DFS on the view tree. The recursive call is not constant but it is a way of traversing the tree.

see the link for more details: https://en.wikipedia.org/wiki/Depth-first_search

Upvotes: 3

Related Questions