CODEWITHSUNDEEP
c#algorithmperformanceforeach
Raoul Sbarberi
Raoul Sbarberi

Reputation: 11

Time Complexity - Which between these two algorithms is faster?

Description

The goal of this program is to populate an orderList from the users orders and a productList foreach of those order. (Please ignore possible syntax errors from this pseudo-C#-code)

Data Structures

class User {
    List<Order> orders; 
}

class Order {
    List<Product> products;
}

class Product {
    int price;
}

List<User> userList = GetUsersFromDB();

List<Order> orderList     = new List<Order>();  
List<Product> productList = new List<Product>();

First Version

foreach(User u in userList) {
    foreach(Order o in u.orders) {
        orderList.Add(o);
        foreach(Product p in o.products) {
            productList.Add(p);
        }
    }
}

Second Version

foreach(User u in userList) {
    foreach(Order o in u.orders) {
        orderList.Add(o);
    }
}

foreach(Order o in orderList) {
    foreach(Product p in o.products) {
        productList.Add(p);
    }
}

My thoughts

Therefore the second program is faster, correct?

Upvotes: 1

Views: 100

Answers (1)

Chris
Chris

Reputation: 27609

Overview

Your analysis for the second case is wrong. Since you have one entry in orderlist for each of the inner things of the first loop the foreach(Order o in orderList) is looping over n^2 items. Having said that there is a disclaimer that n isn't very meaningful here since it is representing multiple things.

Better is to look at it using u, o and p instead.

Case 1

The first one is clearly O(uop).

Case 2

This case has two sets of loops. The first pair of loops is O(uo) as you'd expect..

The second pair of loops then starts with a loop of uo items and then an inner loop of O(p) so the second pair is O(uop). Overall this makes it O(uo)+O(uop) which is equivalent to O(uop), the same as case 1.

Essentially the second case just moves things around a bit, it hasn't actually changed the fundamental algorithm at all.

Real world

As always though if you are actually caring about real world performance rather than just theoretical algorithmic complexity (which isn't always useful when looking at specific cases) then benchmark the performance of your two techniques.

Upvotes: 7

Related Questions