Time complexity of fruit basket

joey_y_feng · August 30, 2022, 5:45pm

Why is time complexity of fruit basket O(N + N)? There is an outer for loop and inner while loop. Outer loop iterates through each character, and inner while loop processes the entire map for each iteration. So shouldn’t this be O(N^2)?

I realized i’m looking at javascript solution and perhaps other implementations are more efficient, but at least for javascript the time complexity looks off

Course: Grokking the Coding Interview: Patterns for Coding Questions - Learn Interactively
Lesson: Fruits into Baskets (medium) - Grokking the Coding Interview: Patterns for Coding Questions

Muntha_Amjad · August 31, 2022, 5:36am

Hi @joey_y_feng
The outer for loop runs for all characters, and the inner while loop processes each character only once; therefore, the time complexity of the algorithm will be O(N+N), which is asymptotically equivalent to O(N).
Hope it will help, Thank you