Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Examples to Understand Time Complexity.
int sum(vector<int> nums) {
int ans = 0; // 1
for (int i=0; i<nums.size(); i++) { // n times
ans += nums[i]; // 1
}
return ans; // 1
}
void efficient(vector<int> nums) {
int addition = sum(nums); // O(n). Note: Single line does not
// mean constant time.
for (int i=0; i<n; i++) { // n times
nums[i] = nums[i] + addition; // 1
}
}
void inefficient(vector<int> nums) {
for (int i=0; i<n; i++) { // n times
nums[i] = nums[i] + sum(nums); // O(n)
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment