Độ phức tạp tính toán (computational complexity) của thuật toán Apriori có thể bị ảnh hưởng bởi các yếu tố sau:
Ngưỡng hỗ trợ (Support Threshold)
Giảm ngưỡng hỗ trợ dẫn đến các tập mục lớn hơn được xác định là thường xuyên. Điều này có tác động không lợi cho độ phức tạp tính toán của thuật toán vì nhiều tập mục ứng viên (candidate itemsets) hơn phải được tạo và đếm.
Kích thước tối đa của tập mục thường xuyên cũng có xu hướng cải thiện với ngưỡng hỗ trợ thấp hơn. Khi kích thước tối đa của tập mục thường xuyên cải thiện, thuật toán sẽ được yêu cầu tạo nhiều lần lặp hơn qua tập dữ liệu.
Số lượng Mặt hàng (Số chiều - Dimensionality)
Khi số lượng mặt hàng khác nhau tăng, nhiều không gian hơn sẽ được yêu cầu để lưu số đếm hỗ trợ của các mặt hàng. Nếu số mặt hàng thường xuyên cũng tăng với số chiều của dữ liệu, giá trị tính toán và I/O sẽ tăng vì số lượng tập mục ứng viên cao hơn được tạo bởi thuật toán.
Số lượng Giao dịch (Number of Transactions)
Vì thuật toán Apriori tạo các lần lặp lại qua tập dữ liệu, thời gian chạy của nó tăng với số lượng giao dịch cao hơn.
Chiều rộng giao dịch trung bình (Average Transaction Width)
Đối với tập dữ liệu dày đặc (dense data sets), chiều rộng giao dịch trung bình có thể cao. Điều này ảnh hưởng đến độ phức tạp của thuật toán Apriori theo hai cách: kích thước tối đa của tập mục thường xuyên có xu hướng tăng khi chiều rộng giao dịch trung bình tăng. Chiều rộng giao dịch tăng, các tập mục lớn hơn được bao gồm trong giao dịch. Điều này sẽ tăng số lần duyệt cây băm (hash tree traversals) được thực hiện trong đếm hỗ trợ (support counting).
Tạo tập mục 1-itemset thường xuyên (Generation of frequent 1-itemsets)
Đối với mỗi giao dịch, cần cập nhật số đếm hỗ trợ cho mỗi mặt hàng hiện diện trong giao dịch. Xét rằng w là chiều rộng giao dịch trung bình, thao tác này cần thời gian O(Nw), nơi N là tổng số giao dịch.
Tạo ứng viên (Candidate generation)
Để tạo tập mục ứng viên k-itemset, các cặp tập mục thường xuyên (k-1)-itemset được kết hợp để quyết định xem chúng có tối thiểu k-2 mặt hàng chung hay không. Mỗi phép kết hợp (merging operation) cần tối đa k-2 so sánh bình đẳng. Trong trường hợp tốt nhất, mỗi bước kết hợp tạo ra một tập mục ứng viên k-itemset khả thi.
Trong trường hợp xấu nhất, thuật toán phải kết hợp mỗi cặp tập mục thường xuyên (k-1)-itemset tìm thấy trong lần lặp trước. Do đó, tổng chi phí kết hợp tập mục thường xuyên là:
$$\mathrm{\displaystyle\sum\limits_{k=2}^w\:(k-2)|C_{k}|<\:Cost\:of\:merging\:<\displaystyle\sum\limits_{k=2}^w\:(k-2)|F_{k-1}|^2}$$
Một cây băm (hash tree) cũng được tạo trong quá trình tạo ứng viên để lưu các tập mục ứng viên. Do độ sâu tối đa của cây là k, chi phí cho việc điền cây băm với các tập mục ứng viên là O($\mathrm{\displaystyle\sum\limits_{k=2}^w\:k|C_{k}|}$).
Trong cắt tỉa ứng viên (candidate pruning), cần kiểm tra rằng các tập con k-2 của mỗi tập mục ứng viên k-itemset là thường xuyên. Vì chi phí tra cứu một ứng viên trong cây băm là O(k), bước cắt tỉa ứng viên cần O($\mathrm{\displaystyle\sum\limits_{k=2}^w\:k|C_{k}|}$) thời gian.