# I don't understand my prof's notes relating to time complexity

In summary: O(f(n)) is that it is a set. g(n) is in the set O(f(n)) if there is some n0, such that for all m > n0, g(n) <= cf(n), for some c.
Problem Statement: I've attached a picture of his notes. For a sorted array, to update it he put: O(logn)+O(1)
Relevant Equations: O(n) + O(logn) = O(n)

I don't see how it can be O(logn)+O(1) and not O(logn)+O(n) in the worst case

After you find the index that needs updating, and you actually change the value (which is O(1),) since it is a sorted array, let's assume that the last element of that has a value gets updated and now it's updated value belongs to the very front of the array. We would have to then move (n-1) elements and make one assignment. How is that not O(n)?

[Moderator's note: Moved from a homework forum.]

#### Attachments

• Lecture 1 002.txt
1 KB · Views: 224
Last edited by a moderator:
Attachment File:
Abstract Data Type: ADT

Organization of a Graph:

Required Operations:
- CRUD: Create (Insert), Retrieve (Find), Update, Delete

Implementation:

Note:
A - Array
O(logN) + O(N) --> O(N)
O(logN) + Lazy O(1) --> O(logN)
O(N) or Lazy O(1) --> O(N)

Insert     Find
Create   Retrieve   Update             Delete
Sorted A       O(N)      O(logN)  O(logN) + O(1)   O(logN) + (O(N) or Lazy O(1))
UnSorted A     O(1)      O(N)*    O(N) + O(1)      O(N) + (O(N) or Lazy O(1))
Sorted LL      O(N)      O(N)     O(N) + O(1)      O(N) + O(1) for link movement
Unsorted LL    O(1)      O(N)     O(N) + O(1)      O(N) + O(1)

* you cannot perform binary search

Notes:
Capacity of the array: The number of elements the array can hold (english size)
Size of the array: The number of elements the array is holding

Question:
1. Why don't we do lazy deletion in a LL

After you find the index that needs updating, and you actually change the value (which is O(1),) since it is a sorted array, let's assume that the last element of that has a value gets updated and now it's updated value belongs to the very front of the array. We would have to then move (n-1) elements and make one assignment. How is that not O(n)?
I suspect that the "update" in question involves a modification of data in the accessed record rather than its key.

An update that affects the key could be modeled as a delete of the old record followed by an insert of the replacement record.

jim mcnamara
jbriggs444 said:
I suspect that the "update" in question involves a modification of data in the accessed record rather than its key.

An update that affects the key could be modeled as a delete of the old record followed by an insert of the replacement record.

jbriggs444
And thank you for closing the loop. Always appreciated.

Not sure what your professor expects, but the correct way to view O(f(n)) is that it is a set. g(n) is in the set O(f(n)) if there is some n0, such that for all m > n0, g(n) <= cf(n), for some c.

Considering numeric addition isn't even defined for sets, what you are writing doesn't even parse logically unless you take + to be the union. Considering that O(1) is a subset of O(n), the union of O(n) and O(1) is just O(n). Likewise, the union of O(logn) and O(n) is just O(n). In other words, the union of O(n) and O(logn) means every function that is either in O(n) or in O(logn). But O(n) contains all of the functions in O(logn).

I think people tend to use + and = with Big-O notation when trying to teach the concept to people who don't know the basics of sets. You can take + to be the union, and = to mean the left side is an element of the set expressed on the right side when following people using these notations.

Breaking an algorithm into the parts and saying one part is O(f(n)) and the other is O(g(n)) makes sense, but when considering the two parts together you take the union of the two, and end up with just the set that is defined by the function with the larger or equal growth. To see why, work out the fact that O(f(n) + g(n) ) defines the same set as O(f(n)) union O(g(n)).

Last edited:
Jarvis323 said:
Not sure what your professor expects, but the correct way to view O(f(n)) is that it is a set. g(n) is in the set O(f(n)) if there is some n0, such that for all m > n0, g(n) <= cf(n), for some c.
That's not the way it's done in computer science. We simply count here and therefore we can write e.g.
##O(\log n)+O(n) =O(n)## or ##O(n)+O(n)=O(n)##. It makes sense, as we counted ##c_0\cdot n \leq c_1\cdot \log n + c_2 \cdot n \leq (c_1 +c_2)\cdot n = O(n)##.

Sets are completely irrelevant.

Last edited:
At least in the computer science theory courses I’ve taken, sets have been used. Maybe it’s mostly just the professor who taught it.

Without sets, I think it can be confusing, because f(n) is not equal to O(f(n)) it’s = O(f(n)) with = meaning it has this property. Sort of like saying 3 = is an integer. It’s just a convenient abuse of notation for saying 3 has the property that it is an integer, or equivalently, is an element of the set of integers. Then even O(g) = O(f) uses = in a different way than that. And the use of + is also redefined.

If you think about, you are just defining sets anyways.

So for me, using sets seems like a more clean and unambiguous way to think about it. So when I try to help people who are confused about it, I assume that thinking about it in this way will clear up any misunderstanding. You don’t need to redefine any notation.

But in the end it doesn’t matter so long as you understand it and are comfortable with the notation.

Last edited:

## 1. What is time complexity and why is it important?

Time complexity is a measure of the amount of time it takes for an algorithm to run as the input size increases. It is important because it allows us to compare the efficiency of different algorithms and choose the most efficient one for a given problem.

## 2. How is time complexity calculated?

Time complexity is typically calculated by counting the number of operations or steps that an algorithm takes to complete as a function of the input size. This can be represented using Big O notation, which expresses the worst-case scenario for time complexity.

## 3. What are the common notations used for time complexity?

The most common notations used for time complexity are Big O, Big Omega, and Big Theta. Big O represents the upper bound or worst-case scenario, Big Omega represents the lower bound or best-case scenario, and Big Theta represents the average case scenario.

## 4. How can I understand my professor's notes on time complexity better?

One way to better understand your professor's notes on time complexity is to practice implementing algorithms and analyzing their time complexity on your own. You can also seek clarification from your professor or classmates if you are unsure about any specific concepts or notations.

## 5. How can I improve my understanding of time complexity?

To improve your understanding of time complexity, it is important to have a strong foundation in data structures and algorithms. You can also practice solving coding challenges or problems that require analyzing time complexity. Additionally, seeking guidance from your professor or attending study groups can also help improve your understanding.

Replies
1
Views
1K
Replies
1
Views
1K
Replies
2
Views
5K
Replies
2
Views
1K
Replies
17
Views
4K
Replies
1
Views
1K
Replies
12
Views
1K
Replies
1
Views
1K
Replies
4
Views
2K
Replies
20
Views
4K