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

  • Thread starter r0bHadz
  • Start date
186
17
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

Last edited by a moderator:

fresh_42

Mentor
Insights Author
2018 Award
11,065
7,605
Attachment File:
Abstract Data Type: ADT
- Graph for relations (facebook, roadnetwork)

Organization of a Graph:
 - Adjacency List
 - Adjacency Matrix

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

Implementation:

Note:
A - Array
LL - Linked List
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
 

jbriggs444

Science Advisor
Homework Helper
7,490
2,555
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.
 
186
17
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.
and your suspicion was correct! I appreciate the reply :)
 

jbriggs444

Science Advisor
Homework Helper
7,490
2,555
and your suspicion was correct! I appreciate the reply :)
And thank you for closing the loop. Always appreciated.
 
175
38
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:

fresh_42

Mentor
Insights Author
2018 Award
11,065
7,605
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:
175
38
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:

Want to reply to this thread?

"I don't understand my prof's notes relating to time complexity" You must log in or register to reply here.

Related Threads for: I don't understand my prof's notes relating to time complexity

Replies
5
Views
819
  • Posted
Replies
1
Views
10K
  • Posted
Replies
3
Views
13K

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top