Q: Startup disk is full?

Go step by step and test.

1. Start up in Safe Mode.

    http://support.apple.com/kb/PH11212

2. Empty Trash.

   http://support.apple.com/kb/PH13806

3. Disk space / Time Machine ?/ Local Snapshots

  Local backups

   http://support.apple.com/kb/ht4878

4. Delete old iOS Devices Backup.

    iTunes > Preferences > Devices

    Highlight the old Backups , press “Delete Backup” and then “OK”.

    http://support.apple.com/kb/HT4946?viewlocale=en_US&locale=en_US

5. Re-index Macintosh HD.

    This will take a while. Wait until it is finished.

    System Preferences > Spotlight > Privacy

    http://support.apple.com/kb/ht2409

6.Try OmniDiskSweeper. This will give the storage size details of the items.

   https://www.omnigroup.com/more

   Select Macintosh HD and click  “Sweep Selected Drive” at the bottom.

   Delete the files you don’t want to keep.

   Be careful. Delete only the files that can be safely  deleted.

About “Other”:

http://support.apple.com/en-us/HT202867

Do you have Microsoft Outlook on your MacBook Air:

Recently, I constantly got "Startup Disk is full" even when I removed some large files. After I checked all photos, music and movies, I started to suspect Microsoft Outlook, for I had problems with it in the beginning. I tried to find Outlook file directory of Outlook and could not find the directory nor my personal mail file (pst files). So I played around and went to Tools\Run Schedule\Empty Deleted Items Folder, and tried to permanently delete all deleted messages. I was a little concerned when it took about 10 minutes to complete, and has obviously cleaned up multiple folders.

When it's done, I have emptied trash can and shutdown my MacBook Air (Yosemite). When restarted, I was so pleased I got 28GB of system Disk storage back.